LG. Hankson's interesting questions, C language

【 Title Description 】

Hanks Doctor is BT(Bio-Tech, Biotechnology ) Well known experts in the field , His son's name is Hankson. Now? , Just came home from school Hankson I'm thinking about an interesting question .

In class today , The teacher explained how to find two positive integers c1 and c2 The greatest common divisor and the least common multiple of . Now? Hankson Think you have mastered this knowledge , He began to think about a “ Find common divisor ” and “ Common multiple ” Something like that “ Inverse problem ”, This is the problem ： We know positive integers a0,a1,b0,b1a0,a1,b0,b1, Let some unknown positive integer x Satisfy ：

1. x and a0 The greatest common divisor of a1;

2. x and b0 The minimum common multiple of is b1.

Hankson Of “ Inverse problem ” Is to find the positive integer that satisfies the condition x. But after a little thought , He found such x Not only , It may not even exist . So he began to think about how to solve the problem of x The number of . Please help him solve this problem by programming .

【 I / O format 】

• Input format

The first line is a positive integer n, Express n Group input data . Next n Each row has a set of input data , Is four positive integers a0,a1,b0,b1, Every two integers are separated by a space . Input data guarantee a0 Can be a1 to be divisible by ,b1 Can be b0 to be divisible by .

• Output format

The output result of each group of input data occupies one line , It's an integer .

For each set of data ： If there is no such x, Please export 0;

If there is such a x, Please output the qualified x The number of .

【 I/o sample 】

• sample input

2 
41 1 96 288
95 1 37 1776

• sample output

6 
2

【 Sample explanation 】

The first set of input data ,x It can be 9、18、36、72、144、288, share 6 individual .

The second set of input data ,x It can be 48、1776, share 2 individual .

【 Data range 】

about 50% The data of , Guaranteed 1≤a0,a1,b0,b1≤10000 And n≤100.

about 100% The data of , Guaranteed 1≤a0,a1,b0,b1≤2000000000 And n≤2000.

About this question , First of all, it is easy to know the meaning of the question x The scope of is in 1 To b1 Between .

therefore , Further, it is easy to think from 1 To b1 Enumerate , If gcd(x,a0)==a1  And lcm(x,b0)==b1 Just cnt++.

as follows ：

for(x = 0;x <= b1;x++)
{
    if((gcd(x,a0)==a1) && (lcm(x,b0)==b1))
    {
         cnt++;
    }
}

However , Doing so will time out .

because a1 yes x,a0 Maximum common factor of ,b1 yes x,b0 The least common multiple of .

So the conditions are met x It must be b1 The factor of ,a1 Multiple .

So we just need to enumerate b1 The factor of ： When you get b1 When a factor of , Its other factor is also determined , So we just need to enumerate to sqrt(b1) that will do .

Finally, pay attention to the range of data .

#include <stdio.h>

long long gcd(long long m,long long n)
{
    return n ? gcd(n,m%n):m;
}

long long lcm(long long m,long long n)
{
    return m*n/gcd(m,n);
}

int main()
{
    long long a0,a1,b0,b1,x,i;
    int n,cnt;
    scanf("%d",&n);
    while(n--)
    {
        cnt = 0;
        scanf("%lld%lld%lld%lld",&a0,&a1,&b0,&b1);
        for(x = 1;x*x <= b1;x++)
        {
            if(b1 % x==0)
            {
                if((gcd(x,a0)==a1) && (lcm(x,b0)==b1))
                    cnt++;
                if((b1/x!=x)&&(gcd(b1/x,a0)==a1) && (lcm(b1/x,b0)==b1))
                    cnt++;
            }
        }
        printf("%d\n",cnt);
    }
	return 0;
}