c/c++语言开发共享洛谷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$的约 …


题意

题目链接

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;  }

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ctvol.com/c-cdevelopment/606642.html

(0)
上一篇 2021年5月14日
下一篇 2021年5月14日

精彩推荐