CF-66D普及+/提高
构造数列
⏱ 2.0s💾 256MB
📋 题目描述
构造一个长度为 的整数序列,要求满足下列三个条件:()任意两数的最大公约数不等于 ;()所有数的最大公约数等于 ;()任意两数互不相同 。
若有多组解,输出任意一组;若无解,输出
📥 输入格式
仅有一个整数 ( ) ,表示要构造的序列的长度 。
📤 输出格式
如果有解则输出 ,每行包含最多不超过 位的整数,否则输出 。如果有多组解则输出任意一组。
📝 样例 1
输入
3
输出
99 55 11115
📝 样例 2
输入
4
输出
385 360 792 8360
📚 来源
Problem:CF-66D
💡 题目讲解
1
理解题意
构造 个不同的整数,满足三个条件:
- 条件 ①:任意两个数的 (两两不互质)
- 条件 ②:所有 个数的 (没有公共因子)
- 条件 ③:互不相同
条件 ① 和 ② 看起来矛盾?其实不然——两两之间有公共因子,但全体没有同一个公共因子。
以 为例,三个质数 :
令 。每个数是 除以一个质数:
验证:
- ✓(都有因子 5)
- ✓(都有因子 2)
- ✓(都有因子 3)
- ✓(15缺2,10缺3,6缺5,没有公共因子)
- 互不相同 ✓
💡 每个数缺不同的质数 → 两两总能找到共同缺的质数之外的因子,但全体没有共同因子。
1 / 5