数论の基础--洛谷P 1072 Hanksonの趣味题

gcd(x,a 0)=a 1 lcm(x,b 0)=b 1の2つの式を与え、a 0,a 1,b 0,b 1は既知であり、xがどれだけ満たされているかを聞く.
标题:まず2つの前置き知識が必要で、証明するならこのブログを見てください.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実は直接使えることを覚えています
これは2つの式が変形する過程である.最後の2つの式が得られた.
このようにすれば、xは必ずb 1より小さいものであり、ましてb 1はxを除去できるので、xはb 1の因子に違いない.私たちはb 1のすべての因子を列挙することによって、xがa 1を除去できるかどうかを判断し、この2つの式を満たすかどうかを判断し、満足すれば答えを1つ加える.
なお,我々が列挙するときはsqrt(b 1)を列挙するだけであり,一つの因子に達すると,もう一つはb 1/xで得られる.
コード:

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include 
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;
}