https://www.luogu.com.cn/problem/P1029

复习一下辗转相除法

int gcd(int a, int b){
    if(b == 0){
        return a;
    }
    return gcd(b, a % b);
}

最小公倍数*最大公约数=P*Q

我的ac代码

#include<iostream>
#include<algorithm>
using namespace std;
int gcd(int a, int b){
    if(b == 0){
        return a;
    }
    return gcd(b, a % b);
}
int main(){
    int x0, y0;
    cin >> x0 >> y0;
    int re = 0;
    for (int p = 2; p <= y0; p++){
        if((x0 * y0) % p == 0){
            int q = (x0 * y0) / p;
            int maxn = max(p, q);
            int minn = min(p, q);
            if(gcd(maxn, minn) == x0){
                int a = p / x0;
                    int b = q / x0;
                    if(a * b * x0 == y0){
                        // cout << p << " " << q << endl;
                        re++;
                    }
            }
        }
    }
    cout << re << endl;
    return 0;
}

看题解好像要考虑的东西还挺多，下面这个是大佬的，要考虑爆int和\(x_0\times y_0\)是完全平方数的情况

#include <bits/stdc++.h>
using namespace std;
long long x,y;
inline long long gcd(long long x,long long y)
{
	if(y==0) return x;
	return gcd(y,x%y);
}
int main()
{
	cin>>x>>y;
	long long ans=0;
	for(long long i=1;i<=sqrt(x*y);i++)
	{
		if(x*y%i==0&&gcd(i,x*y/i)==x) ans++;
	}
	ans*=2;
  	if(x==y) ans--;
   	cout<<ans;
	return 0;
}