传送门
大致思路：
找办法确定x的范围
我们联想到gcd，lcd对于唯一分解定理的运用
即a,b,gcd(a,b)分解质因数后，gcd(a,b)每个质因子的次数是min(在a中出现的次数，b中出现的次数)
lcm变成max即可
那么也就是说 我们可以给a1,a0,b1,b0分解质因数，从而通过 每个质因子次数作比较 来推断x的取值范围
假设px,p0,p1分别是某个质因子在x,a0,a1里的次数
则有 { 1.若p0<p1 那么不满足gcd的关系，需舍掉（因为是取min） 2.若p0=p1 那么px可以取无限大 只要大于p1 3.若p0>p1 那么px只能取p1 }
lcm同理。
由于数的范围很大，2,000,000,000，我们肯定不能筛2,000,000,000以内的质数，考虑到每个数最多只拥有一个大于根号的质因子，我们只需筛到sqrt(2,000,000,000)~=50000即可，最后一个特大数再特判。
具体看代码注释
#include<bits/stdc++.h> using namespace std; int prime[10005],cnt; bool vis[50005]; void Euler_pick(int n) { memset(vis,false,sizeof(false)); for(int i=2;i<=n;i++) { if(!vis[i]) prime[++cnt]=i; for(int j=1;i*prime[j]<=n;j++) { vis[i*prime[j]]=true; if(i%prime[j]==0) break; } } } int main() { Euler_pick(50000); int T; cin>>T; while(T--) { int a0,a1,b0,b1,ans=1; bool flag=false; cin>>a0>>a1>>b0>>b1; if(a1>a0||b1<b0) { cout<<"0"<<'\n'; continue; } for(int i=1;i<=cnt;i++) { if(a0==a1==b0==b1==1) break; int ka0=0,ka1=0,kb0=0,kb1=0; while(a0%prime[i]==0) {ka0++;a0/=prime[i];} while(a1%prime[i]==0) {ka1++;a1/=prime[i];} while(b0%prime[i]==0) {kb0++;b0/=prime[i];} while(b1%prime[i]==0) {kb1++;b1/=prime[i];} if(ka0<ka1||kb0>kb1) {flag=true;break;} int l1=ka1,l2=0,r1=100000,r2=kb1; //l1,l2分别是两个式子的下界限制，r1,r2是上界限制 //由唯一分解定理可知 /* 对于gcd { 若ka0=ka1 此时是没有上界的 r1无限大 l1就是ka1 若ka0>ka1 此时kx只能取ka1 所以l1=r1=ka1 } 对于lcm { 若kb0=kb1 此时是有上界的 r2为kb1 没有下界 若kb0<kb1,此时kx只能取kb1 所以l2=r2=kb2 从此可以看出r2=kb1 } 这里我们代码的写法偷一点懒 */ if(ka0>ka1) r1=ka1; if(kb0<kb1) l2=kb1; int l=max(l1,l2); int r=min(r1,r2);//小小取大，大大取小 if(r<l) {flag=true;break;}; ans=(long long)ans*(r-l+1); } //分解sqrt范围内数据完毕 此时可能会有一个大于50000的质因子存在 if(!(a0==1&&a1==1&&b0==1&&b1==1)) { if(a0<a1||b0>b1) flag=true; if(a1==a0&&a1!=1) ans*=2;//a1==a0保证了剩下的数就是某个大质因子 而不是从上面break下来的 if(b1==b0&&b1!=1) ans*=2; } if(flag==true) ans=0; cout<<ans<<'\n'; } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9643906.html
相关资源：各显卡算力对照表！