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

输入二个正整数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);
}