Hankson 的趣味题

P1072 [NOIP2009 提高组] Hankson 的趣味题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

• 由gcd（a0,x)=a1可以有gcd(a0/a1,x/a1)=1
• 由lcm(b0,x)=b1又lcm(b0,x)*gcd(b0,x)=b0*x得gcd(b0,x)=b0*x/b1得到gcd(b1/x,b1/b0)=1
• 根据推理有gcd（a0/a1,x/a1)=1,gcd(b1/x,b1/b0)=1
• 计算：
  • 从1遍历到sqrt(b1),满足上面两个式子ans++
    • 同时要满足b1%i==0，还要考虑b1/i这个情况

// 2
// 41 1 96 288
// 95 1 37 1776
#include <bits/stdc++.h>
using namespace std;
#define N 1e5
#define INF 2e9
#define MAX 10000000
// https://www.luogu.com.cn/problem/P1072
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int a0, a1, b0, b1;
int t;
int a01, b10;
int main()
{
    cin >> t;
    while (t--)
    {
        int ans = 0;
        scanf("%d%d%d%d", &a0, &a1, &b0, &b1);
        a01 = a0 / a1, b10 = b1 / b0;
        for (int i = 1; i <= sqrt(b1); i++)
        {
            if (b1 % i == 0)
            {
                int j = b1 / i;
                if (i % a1 == 0 && gcd(b10, b1 / i) == 1 && gcd(a01, i / a1) == 1)
                    ans++;
                if (i == j)
                    continue;
                if (j % a1 == 0 && gcd(b10, b1 / j) == 1 && gcd(a01, j / a1) == 1)
                    ans++;
            }
        }
        printf("%d\n", ans);
    }
}