本文共 1904 字，大约阅读时间需要 6 分钟。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define debug() puts("++++")#define gcd(a,b) __gcd(a,b)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define fi first#define se second#define pb push_back#define sqr(x) ((x)*(x))#define ms(a,b) memset(a,b,sizeof(a))#define sz size()#define be begin()#define pu push_up#define pd push_down#define cl clear()#define lowbit(x) -x&x#define all 1,n,1#define mod 998244353#define pi acos(-1.0)#define rep(i,x,n) for(int i=(x); i<(n); i++)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair P;const int INF = 1<<30;const int maxn = 150000+3;const double eps = 1e-8;const int dx[] = {-1,1,0,0,1,1,-1,-1};const int dy[] = {0,0,1,-1,1,-1,1,-1};int dir[2]={-1,1};const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int t,n,m,d;int cnt=0;LL lcm(LL a, LL b){ return a/__gcd(a,b)*b;}LL cal(LL n){ for(int i=2;i*i<=n;i++) if(n%i==0) return i; return n;}LL a,b,x,y;int main(){ cin>>n>>a>>b; for(int i=1;i >x>>y; a=__gcd(x*y,a); b=__gcd(x*y,b); } if(a!=1) printf("%lld\n",cal(a)); else if(b!=1) printf("%lld\n",cal(b)); else puts("-1");}/*23 11 1 23 21 1 2【题意】给定n对数，求一个WCD，它满足至少能被每对数中的一个整除，若不存在，输出-1。【类型】数论【分析】一开始的思路是求每对数的最小公倍数，然后把这n个最小公倍数求个gcd，然后取其最小因子即可。但这样因为TLE而FST了。后来想想也是，如果每对数中的两个数互质，那么他们的最小公倍数就是1e18左右的大小，求其最小因子的时间复杂度差不多就是1e9，肯定会T。比如下面这组样例：21999999973 19999999431999999973 1999999943其实正解想法差不多，就把第一对中的第一个数和后面每对的乘积求一个gcd，第二个数也和后面的每对的乘积求一个gcd，这样就保证这两个数都是小于等于2e9的，求其最小因子的复杂度<1e5，可行。PS：其实并不需要求每对数的最小公倍数，求其乘积即可，因为乘积包括了每对数那2个数中的所有因子，且乘积的最小因子一定能被每对数那2个数中的1个整除。【时间复杂度&&优化】【trick】【数据】
转载于:https://www.cnblogs.com/Roni-i/p/9525530.html