题目：Weakened Common Divisor
题意：
比赛时我的思路是求出每一对ai和bi的lcm，计作ci，再求出gcd(ci)，最后求出这个gcd的一个质因数即可。问题是质因数的分解问题，max{gcd}=1e18，如果要找到质因数最多要做1e9次运算。然后我就被hack掉了…
hack数据：
1
1000000007 1000000009正确思路：将a1和b1分解质因数，对于每个质因数，判断是否能被每个数对整除。复杂度O(n n??√ n )。
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 200000
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define rep2(i,x,y) for(int i=y;i>=x;i--)int n;
int a[maxn+5],b[maxn+5];void read(int& x) {scanf("%d",&x);
}void print(int x) {printf("%d",x);
}vector<int> vec;void slv(int x) {for(int i=2;i*i<=x;i++) {if(x%i==0) {vec.push_back(i);while(x%i==0) x/=i;}}if(x>1) vec.push_back(x);
}int main() {read(n);rep(i,1,n) {read(a[i]),read(b[i]);}slv(a[1]),slv(b[1]);rep(i,0,vec.size()-1) {int x=vec[i];rep(j,1,n) {if(a[j]%x&&b[j]%x) goto END;}print(x);return 0;END:;}print(-1);return 0;
}