美文网首页
noip2001pj T2 最小公倍数和最大公约数问题

noip2001pj T2 最小公倍数和最大公约数问题

作者: KingSann | 来源:发表于2016-11-26 21:32 被阅读0次
    输入二个正整数x0,y0(2≤x0≤100000,2≤y0≤1000000),求出满足下列条件的P、Q的个数。
    
    条件:1.P、Q是正整数
    2.要求P、Q以xO为最大公约数,以yO为最小公倍数。
    试求,满足条件的所有可能的两个正整数的个数。
    

    看完之后第一眼暴力,然后发现暴力貌似O(n^2)会炸,然后开始分析如何解决。。

    首先,众所周知lcm(a,b)=a*b/gcd(a,b),那么我们就可以把P、Q表示出来了。

    P>=x
    Q>=x
    gcd(P,Q)=x
    lcm(P,Q)=y
    

    那么我们看一下以后一个式子,将gcd带进去。

    lcm(P,Q)=P*Q/gcd(P,Q)=P*Q/x=y
    P*Q=x*y
    Q=x*y/P
    

    好了,也就是说我们可以根据P求出Q的值,也就是说枚举P就可以了,所以O(n^2)下降到了O(n)。

    #include <iostream>
    #include <algorithm>
    #include <cstdio>
    using namespace std;
    
    typedef long long int t;
    t x,y,ans;
    inline t gcd(t a,t b){return b?gcd(b,a%b):a;}
    int main(){
        scanf("%lld%lld",&x,&y);
        for(int i=1;i*x<=y;i++)
            ans+=!(y%i)&&gcd(i*x,y/i)==x;
        printf("%lld\n",ans);
    }

    相关文章

      网友评论

          本文标题:noip2001pj T2 最小公倍数和最大公约数问题

          本文链接:https://www.haomeiwen.com/subject/fcpgpttx.html