洛谷P1072 Hankson 的趣味题(数学)

题意

Sol

充满套路的数学题。。

如果你学过莫比乌斯反演的话不难得到两个等式

\[gcd(\frac{x}{a_1}, \frac{a_0}{a_1}) = 1
\]

\[gcd(\frac{b_1}{b_0}, \frac{b_1}{x}) = 1
\]

然后枚举\(b_1\)的约数就做完了。。

// luogu-judger-enable-o2

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define LL long long

using namespace std;

const int MAXN = 1e6;

inline int read() {

    char c = getchar(); int x = 0, f = 1;

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int T, a0, a1, b0, b1, ans;

int gcd(int a, int b) {

    return b == 0 ? a : gcd(b, a % b);

}

void check(int x) {

    if(x % a1) return ;

    ans += (gcd(x / a1, a0 / a1) == 1 && gcd(b1 / b0, b1 / x) == 1);

}

int main() {

    T = read();

    while(T--) {

        a0 = read(), a1 = read(), b0 = read(), b1 = read(); ans = 0;

        for(int x = 1; x * x <= b1; x++) {

            if(b1 % x == 0) {

                check(x);

                if(b1 != x) check(b1 / x);

            }

        }

        cout << ans << endl;

    }

    return 0;

}

巴特西

洛谷P1072 Hankson 的趣味题(数学)

题意

Sol

最新文章

热门文章