F - Petya and His Friends CodeForces - 66D（数论，素数构造）

本文主要是介绍F - Petya and His Friends CodeForces - 66D（数论，素数构造），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Examples
Input
3
Output
99
55
11115
Input
4
Output
385
360
792
8360

题意： 构造题，构造n个不相同的数，任意两个数gcd不等于1，所有数的gcd等于1.
思路： 个人认为这场最有想头的一道题目。最暴力的思路是打表搞出n个质数，第一个数除了第一个质数不选其他都选相乘，第二个数除了第二个数不选其他都选相乘。当然数据范围是承受不了的（或许你可以开大整数？）

分析一下问题本身的条件，我们要保证任意两个的gcd！=1，那么任意两个数必须得有一个公因子。对于让所有的数gcd = 1这个条件，上面原始思路的做法是打出n个质数，然后考虑每次让一个质数“缺席”，仔细分析这个条件，我们需要这么多质数和这么多“缺席”来保证gcd = 1吗？反向推太麻烦了，正向推一边，两个数gcd = 1,那就得没有公共因数，但是3个数gcd =
解法有两种，构造6 10 15 156 1566 15666。。。还可以状态压缩（嗯，真是个好东西），考虑出一些素数的组合。（太晚了，思路明天再补吧）

UPD：
又看了一下这题，其实好想。全部的GCD为1，只要保证每一个质数因子的最小出现次数都为0就好了。任意两个不为1，只要你在前n-1个数里面放一个公因子，后n-1个数里面再放另一个公因子，第一个和最后一个再放一个公因子就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>using namespace std;
typedef long long ll;const int maxn = 1000 + 7;int a[maxn];
int vis[maxn],prime[maxn];void getprime()
{vis[2] = 0;for(int i = 2;i < maxn;i++){if(vis[i] == 1)continue;prime[++prime[0]] = i;for(int j = i * i;j < maxn;j += i){vis[j] = 1;}}
}int main() {int n;scanf("%d",&n);if(n == 2) {printf("-1\n");return 0;}getprime();a[1] = 10; a[n] = 15;for(int i = 2;i < n;i++) {a[i] = 6 * prime[i + 5];}for(int i = 1;i <= n;i++) {printf("%d\n",a[i]);}return 0;
}