洛谷P1029 最大公约数和最小公倍数问题
题意 给定 x0与y0 求有多少组正整数对(P,Q) 满足 P与Q的最大公约数是x0 最小公倍数是y0
首先我们可以发现x0*y0 == P*Q 那么我们知道 x0 与 y0 的乘积 我们就可以在 O(sqrt(n)) 的时间内枚举他的因数 然后再判断 其公约数是否为 x0 设 w=sqrt(x0*y0) 时间复杂度则为 O(w*log(w))
#include#include #define ll long long using namespace std ;ll xx,yy,x,y,sum,r ;int ans ; ll gcd(ll x,ll y) { if(!y) return x ; return gcd(y,x%y) ; }int main() { scanf("%lld%lld",&xx,&yy) ; sum = xx*yy ; r = sqrt(sum) ; for(ll x=xx;x<=r;x++) { if(sum%x!=0) continue ; y = sum/x ; if(xx==gcd(x,y)) { if(x==y) ans++; else ans+=2 ; printf("%lld %lld\n",x,y) ; } } printf("%d\n",ans) ; return 0 ;}
# include# include int main(){ int x0,y0,h,ratio,factor=0; scanf("%i%i",&x0,&y0); //输入给定的最大公约数x0和最小公倍数y0 if(y0%x0) //如果y0不是x0的倍数 return !puts("0"); //则不存在满足给定最大公约数和最小公倍数的数 for(ratio=y0/x0,h=2;ratio>1;h++) //y0与x0的比值为ratio { //将ratio分解质因数 factor+=!(ratio%h); //可以分解出的质因数的种数为factor while(!(ratio%h)) ratio/=h; //保证分解出的因数h是质数 } return !printf("%.0f\n",pow(2,factor)); //输出满足给定要求的数的对数pow(2,factor)}