NOIP2009 Hankson 的趣味题

大家好，欢迎来到IT知识分享网。

题目：http://www.luogu.org/problem/show?pid=1072#
分析：
1.gcd(x,a0)=a1;
gcd(x/a1,a0/a1)=1;
2.x*b0=b1*gcd(x,b0);
gcd(x,b0)=x*b0/b1;
gcd(b1/b0,b1/x)=1;
然后√n 枚举判断上述两个结论，欧几里得算法是logn，所以时间复杂度是√n*logn
代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int ans;
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    int T,i,j,a0,a1,b0,b1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
        //len=sqrt(b1+0.5);
        ans=0;
        for(i=1;i*i<=b1;i++)
        {
            if(b1%i==0){
                if(i%a1==0&&(gcd(i/a1,a0/a1)==1)&&(gcd(b1/b0,b1/i)==1))
                  ans++;
                j=b1/i;
                if(j%a1!=0||i==j) continue;
                if((gcd(j/a1,a0/a1)==1)&&(gcd(b1/b0,b1/j)==1))
                  ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}