\(Description:\)

给定\(a_0,a_1,b_0,b_1\)，求所有满足\(gcd(x,a_0)=a_1\),\(lcm(x,b_0)=b_1\)的x的个数。

\(Sample\) \(Input\):

2

41 1 96 288

95 1 37 1776

\(Sample\) \(Output\):

6

2

数论题都那么毒瘤吗？

一开始除了暴力毫无思路。。。

暴力：从\(a_1->b_1\)枚举。。。。。。

没有思路，化个式子放松放松:

\(a_0=a_1*k_1\)

\(x=a_1*k_2\)

\(b_1=b_0*k_3\)

\(b_1=x*k_4\)

震惊！发现x是\(a_1\)的倍数，是\(b_1\)的因数。

于是想着随便枚举\(b_1\)的因数，gcd，lcm判断。

喵的过了。。。。。。

要不要看代码呀？

#include
    
     #define int long longusing namespace std;int T,ans;int a0,b0,a1,b1;inline int gcd(int a,int b){    int tmp=0;    while(b){        if(a
    

然而题解里还有一种更强的做法：

首先一个推论：

对于\(gcd(a,b)=c\),\(gcd(a/c,b/c)=1\)

证明：

设\(a=c*k_1\),\(b=c*k_2\)

那么如果推论不成立，那么一定有\(k_1*k_2\)里还有a,b公因数。

那么可以继续拆分

那么原式变为：

\(gcd(x,a_0)=a_1\) \(=>\) \(gcd(x/a_1,a_0/a_1)=1\)

\(lcm(x,b_0)=b1\) \(=>\) \(gcd(b_1/b_0,b_1/x)=1\)

这样枚举范围小一点，照理说会快，然而我却慢了。

#include
    
     #define int long longusing namespace std;int T,ans;int a0,b0,a1,b1;inline int gcd(int a,int b){    int tmp=0;    while(b){        if(a