洛谷p1072 gcd，质因数分解

/* 可以得a>=c,b<=d，枚举d的质因子p 那么a,b,c,d,x中包含的p个数是ma,mb,mc,md,mx 在gcd(a,x)=c中 ma<mc => 无解 ma=mc => mx>=mc ma>mc => mx=mc 在lcm(b,x)=d中 mb<md => mx=md mb=md => mx<=md mb>md => 无解 那么 ma==mc且mb==md时，mc<=mx<=md ma>mc时 mx=mc,mb<md时，mx=md 令cntp表示x包含质因子p的方案数 预处理质数，找出所有d的质因子p，计算cntp，如果d自己也是质数，那么计算一次cntd即可 复杂度O(nsqrt(d)/logd) */ #include<bits/stdc++.h> using namespace std; #define ll long long ll a,b,c,d,x,ma,mb,mc,md,mx,tot,p[1000000]; ll m,prime[1000000],v[1000000]; void init(int n){ memset(v,0,sizeof v); m=0; for(int i=2;i<=n;i++){ if(v[i]==0){ v[i]=i; prime[++m]=i; } for(int j=1;j<=m;j++){ if(prime[j]>v[i] || prime[j]>n/i) break; v[i*prime[j]]=prime[j]; } } } int divide(int n,int p){ int res=0; while(n%p==0)res++,n/=p; return res; } int main(){ init(sqrt(2000000007));//打表 int n; scanf("%d",&n); while(n--){ ll ans=1,cnt,tot=0,flag=0; scanf("%lld%lld%lld%lld",&a,&c,&b,&d); int tmp=d; for(int i=1;i<=m;i++){//求出d的所有质因子 if(prime[i]>d) break; if(d%prime[i]==0) { p[++tot]=prime[i]; while(d%prime[i]==0) d/=prime[i]; } } if(d>1)p[++tot]=d; d=tmp; for(int i=1;i<=tot;i++){ ma=divide(a,p[i]); mb=divide(b,p[i]); mc=divide(c,p[i]); md=divide(d,p[i]); if(ma<mc || mb>md)ans=0;//不可能的情况 else if(ma==mc && mb==md){//两者都有多解 if(mc<=md) ans*=(md-mc+1); else ans=0; } else if(ma==mc && mb<md){//只有一解，可能没有 if(mc>md) ans=0; } else if(mb==md && ma>mc){ if(mc>md)ans=0; } else if(mc!=md) ans=0; if(ans==0) break; } printf("%lld\n",ans); } }

这是进阶指南第一版的一道题，书上有个推论错了，，

转载于:https://www.cnblogs.com/zsben991126/p/10233169.html

相关资源：各显卡算力对照表！