题意：给你n组，每组两个数字，要你给出一个数，要求这个是每一组其中一个数的因数（非1），给出任意满足的一个数，不存在则输出-1。
思路1：刚开始乱七八糟暴力了一下果断超时，然后想到了把每组两个数相乘，然后求每组的GCD，那么这个GCD就是因数的乘积（如果GCD==1就输出-1）。然后打个2e5的素筛表，然后找到GCD的一个素数因数。做到这里好像没问题了，然而，分分钟会被hack，问题出在哪里了？显然啊，打素数表只用2e5的范围，但是因数还包括自己本身啊！所以一旦GCD大于2e5我们就找不到答案了，那么我用一个set来储存遇到的大于2e5的数，如果素筛没找到，那就去set里遍历就行了。
思路2：还是那个问题，大于2e5的素数怎么解决。大佬告诉我一个方法，把第一组数据质因数分解，如果分解到最后发现第一组数据的质因数出现了大于2e5的素数，那么就把他存起来，在后面判断。
混合场很不友好，然而我并没有报名，帮别人掉分（逃
代码1：
#include#include #include #include<set> #include #include<string> #include #include #include #define ll long long #define ull unsigned long long using namespace std; const int maxn = 2e5+13; const int seed = 131; const int MOD = 100013; const int INF = 0x3f3f3f3f; int pr[maxn],p[maxn],pn; set st; void get(){pn = 0;memset(pr,0,sizeof(pr));for(int i = 2;i < maxn;i++){if(!pr[i]){p[pn++] = i;for(ll j = (ll) i * i;j < maxn;j += i){pr[j] = 1;}}} } ull gcd(ull a,ull b){return b == 0? a : gcd(b,a % b); } int main(){int n;get();st.clear();scanf("%d",&n);ull u,v;scanf("%lld%lld",&u,&v);if(u >= maxn) st.insert(u);if(v >= maxn) st.insert(v);ull GCD = u*v;bool flag = true;for(int i = 2;i <= n;i++){scanf("%lld%lld",&u,&v);if(u >= maxn) st.insert(u);if(v >= maxn) st.insert(v);GCD = gcd(GCD,u * v);if(GCD == 1){flag = false;break;}}if(flag){for(int i = 0;i < pn && p[i] * p[i] <= GCD;i++){if(GCD % p[i] == 0){printf("%d\n",p[i]);return 0;}}for(set ::iterator it = st.begin(); it != st.end();++it){ll u = *it;if(GCD % u == 0){printf("%lld\n",*it);return 0;}}printf("%lld\n",GCD);}else printf("-1\n");return 0; }
代码2：
/* author ：竹攸 */ #include#include #include #include using namespace std;const int maxn = 2e5+10; typedef long long ll; ll p[maxn],num[maxn],k,a[maxn],b[maxn];void prime(){for(int i = 2; i < maxn; i++){if(!num[i]){for(ll j = 1LL*i*i; j < maxn; j+=i){num[j] = 1;}}}k = 0;for(int i = 2; i < maxn;i++){if(!num[i])p[++k] = i;} }ll gcd(ll a,ll b){return b == 0?a:gcd(b, a%b); }int main(){int n;ll x, y, a, b, sa, sb;prime();while(scanf("%d",&n)!=EOF){scanf("%lld%lld",&x,&y);num[1] = x*y;if(n == 1){ //n等于1的时候先输出printf("%lld\n",x);continue;}for(int i = 1; i <= k&& x >= p[i]; i++){ //判断x中是否存在大于2e5的素数while(x % p[i] == 0){x /= p[i];}}if(x == 1)a = 2e9+10;elsea = x;for(int i = 1; i <= k&& y >= p[i]; i++){ //y与x 同理while(y % p[i] == 0){y /= p[i];}}if(y == 1)b = 2e9+10;elseb = y;sa = sb = 1;for(int i = 2; i <= n; i++){scanf("%lld%lld",&x,&y);num[i] = x*y;if(x % a == 0 || y % a == 0)sa++;if(y % b == 0|| x % b == 0)sb++;}if(sa == n){printf("%lld\n",a);continue;}else if(sb == n){printf("%lld\n",b);continue;}ll Gcd = num[1];for(int i = 2; i <= n; i++)Gcd = gcd(num[i],Gcd);int ans = 0;for(int i = 1; i <= k;i++){if(Gcd % p[i] == 0){ans = p[i];break;}}if(ans == 0 && Gcd != 1)printf("%lld\n",Gcd);else if(ans == 0 && Gcd == 1)printf("-1\n");elseprintf("%d\n",ans);}return 0; }
转载于:https://www.cnblogs.com/KirinSB/p/9507743.html