🐷大肚肚
CF-66D普及+/提高

构造数列

2.0s💾 256MB

📋 题目描述

构造一个长度为 nn 的整数序列,要求满足下列三个条件:(11)任意两数的最大公约数不等于 11 ;(22)所有数的最大公约数等于 11 ;(33)任意两数互不相同 。

若有多组解,输出任意一组;若无解,输出 1-1

📥 输入格式

仅有一个整数 nn2n502\le n \le 50 ) ,表示要构造的序列的长度 。

📤 输出格式

如果有解则输出 nn ,每行包含最多不超过 100100 位的整数,否则输出 1-1 。如果有多组解则输出任意一组。

📝 样例 1

输入
3
输出
99
55
11115

📝 样例 2

输入
4
输出
385
360
792
8360

📚 来源

💡 题目讲解

1

理解题意

构造 nn 个不同的整数,满足三个条件:

  • 条件 ①:任意两个数的 gcd1\gcd \neq 1(两两不互质)
  • 条件 ②:所有 nn 个数的 gcd=1\gcd = 1(没有公共因子)
  • 条件 ③:互不相同

条件 ① 和 ② 看起来矛盾?其实不然——两两之间有公共因子,但全体没有同一个公共因子。


n=3n=3 为例,三个质数 2,3,52,3,5

P=2×3×5=30P = 2 \times 3 \times 5 = 30。每个数是 PP 除以一个质数

  • a1=30/2=15a_1 = 30 / 2 = 15
  • a2=30/3=10a_2 = 30 / 3 = 10
  • a3=30/5=6a_3 = 30 / 5 = 6

验证:

  • gcd(15,10)=51\gcd(15,10)=5 \neq 1 ✓(都有因子 5)
  • gcd(10,6)=21\gcd(10,6)=2 \neq 1 ✓(都有因子 2)
  • gcd(15,6)=31\gcd(15,6)=3 \neq 1 ✓(都有因子 3)
  • gcd(15,10,6)=1\gcd(15,10,6)=1 ✓(15缺2,10缺3,6缺5,没有公共因子)
  • 互不相同 ✓

💡 每个数缺不同的质数 → 两两总能找到共同缺的质数之外的因子,但全体没有共同因子。

1 / 5