题意：
给定一个长度为n nn的序列a和整数m，求有多少k满足1 < = k < = m并且g c d ( k , a i ) = 1 , 1 < = i < = n , m , a i < = 1 e 5
思路：
gcd(k,ai)=1说明k和每一个a i都没有相同的质因子。
对每个a i
进行质因子分解，对分解出来的因子，类似于质数筛的方法筛去[ 1 , m ]里因子的倍数。最后剩下的数就是合法的k.
时间复杂度O ( n n )
代码：
// Problem: D - Coprime 2 // Contest: AtCoder - AtCoder Beginner Contest 215 // URL: https://atcoder.jp/contests/abc215/tasks/abc215_d // Memory Limit: 1024 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3,"Ofast","inline") #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read(){ll x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;} inline void write(ll x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');} #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b,ll mod){ll res = 1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} const int maxn=1e6+7; int n,m,a[maxn]; vector<int>res,tmp; map<int,bool>mp; int main(){ n=read,m=read; rep(i,1,n){ ll x=read; tmp.clear(); for(ll j=2;j*j<=x;j++) if(x%j==0){ tmp.push_back(j); while(x%j==0) x/=j; } if(x>1) tmp.push_back(x); for(auto t:tmp) if(!mp[t]){ for(ll j=t;j<=m;j+=t) mp[j]=1; } } rep(i,1,m) if(!mp[i]) res.push_back(i); printf("%d\n",res.size()); for(auto t:res) printf("%d\n",t); return 0; }
