数论基础--洛谷P1072 Hankson 的趣味题

题目大意：
给出
gcd(x,a0)=a1
lcm(x,b0)=b1
两个式子，a0，a1，b0，b1是已知的，问有多少个x满足情况。

题解：
首先需要有两个前置知识，证明的话看这篇博客：
https://blog.csdn.net/nuclearsubmarines/article/details/77603154
1.gcd(x,y) * lcm(x,y)=x * y;
2.gcd(x,y)=z , gcd(x/z,y/z)=1
其实记住可以直接用的

这是两个式子变形的过程。得出最后两个公式。

这样的话，x必然是小于b1的，况且b1可以整除x，所以x一定是b1的因子，我们通过枚举b1的所有因子，来判断x是否可以整除a1，并且满足这两个式子，如果满足则答案加一。

注意，我们枚举的时候只需要枚举sqrt(b1)，我们如果的到一个因子，那么另外一个可以用b1/x得出。

代码：

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
const int maxn = 1e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 100000000;
using namespace std;

int main(){
    int t;
    cin>>t;
    while(t--){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        int ans=0;
        for(int x=1;x*x<=d;x++){
            if(d%x==0){
                if(x%b==0&&__gcd(x/b,a/b)==1&&__gcd(d/c,d/x)==1) ans++;
                int xx=d/x;
                if(xx==x) continue;
                if(xx%b==0&&__gcd(xx/b,a/b)==1&&__gcd(d/c,d/xx)==1) ans++;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}