#include <iostream> #include <cstdio> #include <cmath> using namespace std; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } int main() { int n; cin >> n; while (n-- > 0) { int a0, a1, b0, b1, ans = 0; cin >> a0 >> a1 >> b0 >> b1; int p = a0 / a1, q = b1 / b0; for (int i = 1; i <= sqrt(b1); i++) if (b1 % i == 0) { if ((i % a1 == 0) && (gcd(i / a1, p) == 1) && (gcd(q, b1 / i) == 1)) ans++; int j = b1 / i; if (i == j) continue; if ((j % a1 == 0) && (gcd(j / a1, p) == 1) && (gcd(q, b1 / j) == 1)) ans++; }

7.[NOIP2009 提高组] Hankson 的趣味题 难度：普及/提高- 来源：NOIP提高组 题目描述 Hanks 博士是 BT（Bio-Tech，生物技术) 领域的知名专家，他的儿子名叫 Hankson。现在，刚刚放学回家的 Hankson 正在思考一个有趣的问题。 今天在课堂上，老师讲解了如何求两个正整数 c1 和 c2的最大公约数和最小公倍数。现在 Hankson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数 a0,a1,b0,b1 ，设某未知正整数 x 满足： 1.x 和 a0 的最大公约数是 a1； 2.x 和 b0 的最小公倍数是 b1。 Hankson 的“逆问题”就是求出满足条件的正整数 x。但稍加思索之后，他发现这样的 x 并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的 x 的个数。请你帮助他编程求解这个问题。 输入格式 第一行为一个正整数 n，表示有 n 组输入数据。接下来的$ n$ 行每行一组输入数据，为四个正整数a0,a1,b0,b1，每两个整数之间用一个空格隔开。输入数据保证 a0 能被 a1 整除，b1 能被 b0 整除。 输出格式 共 n 行。每组输入数据的输出结果占一行，为一个整数。 对于每组数据：若不存在这样的 x，请输出 00，若存在这样的 x，请输出满足条件的 x 的个数； 输入输出样例 输入#1 2 41 1 96 288 95 1 37 1776 输出#1 6 2 AC代码（C++）： 没有注释，自行学习。 by：ACGO 你的点赞和关注就是我更新题解的最大动力！ 点个赞吧 ↓ ！

#include <iostream> #include <cstdio> #include <cmath> using namespace std; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } int main() { int n; cin >> n; while (n-- > 0) { int a0, a1, b0, b1, ans = 0; cin >> a0 >> a1 >> b0 >> b1; int p = a0 / a1, q = b1 / b0; for (int i = 1; i <= sqrt(b1); i++) if (b1 % i == 0) { if ((i % a1 == 0) && (gcd(i / a1, p) == 1) && (gcd(q, b1 / i) == 1)) ans++; int j = b1 / i; if (i == j) continue; if ((j % a1 == 0) && (gcd(j / a1, p) == 1) && (gcd(q, b1 / j) == 1)) ans++; } return 0; }

远古时期代码忘了lcm（）

#pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #include <cstdio> #include <vector> #include <algorithm> using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 45000; vector<int> get_primes(int x) { vector<int> primes; vector<bool> st(x + 1); for (int i = 2; i <= x; i++) { if (!st[i]) { primes.push_back(i); } for (int j = 0; j < primes.size() && primes[j] <= x / i; j++) { st[i * primes[j]] = true; if (i % primes[j] == 0) break; } } return primes; } int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } void dfs(int u, int p, const vector<PII>& factor, vector<int>& divider) { if (u >= factor.size()) { divider.push_back(p); return; } int power = factor[u].second; int factorVal = factor[u].first; for (int i = 0; i <= power; i++) { dfs(u + 1, p, factor, divider); p *= factorVal; } } int main() { vector<int> primes = get_primes(N); int t; scanf("%d", &t); while (t--) { int a0, a1, b0, b1; scanf("%d %d %d %d", &a0, &a1, &b0, &b1); }

CP突然警觉002591.[NOIP2009 提高组] Hankson 的趣逝题 题 不 解 所以Hankson的趣逝题和Hanks是不是BT砖家有什么关系啊

#include <bits/stdc++.h> int gcd(int a, int b) {return !b ? a : gcd(b, a % b);} int lcm(int a, int b) {return a / gcd(a, b) * b;} int main(int argc, char const *argv[]) { int T, a0, a1, b0, b1; std::cin >> T; while (T--) { scanf("%d%d%d%d", &a0, &a1, &b0, &b1); int kn = sqrt(1.0 * b1), ans = 0; for (int i = 1; i <= kn; i++) if (b1 % i == 0) { if (gcd(i, a0) == a1 and lcm(i, b0) == b1) ans++; if (i != b1 / i and gcd(b1 / i, a0) == a1 and lcm(b1 / i, b0) == b1) ans++; } printf("%d\n", ans); } return 0; }

话不多说，请看题解~

这个人↓

#include <iostream> #include <cstdio> #include <cmath> using namespace std; int gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b); } int main(){ int n; cin >> n; while (n-- > 0){ int a0, a1, b0, b1, ans = 0; cin >> a0 >> a1 >> b0 >> b1; int p = a0 / a1, q = b1 / b0; for (int i = 1; i <= sqrt(b1); i++) if (b1 % i == 0){ if ((i % a1 == 0) && (gcd(i / a1, p) == 1) && (gcd(q, b1 / i) == 1)) ans++; int j = b1 / i; if (i == j) continue; if ((j % a1 == 0) && (gcd(j / a1, p) == 1) && (gcd(q, b1 / j) == 1)) ans++; } cout << ans << endl; } return 0; }

#pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #include <cstdio> #include <vector> #include <algorithm> using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 45000; vector<int> get_primes(int x) { vector<int> primes; vector<bool> st(x + 1); for (int i = 2; i <= x; i++) { if (!st[i]) { primes.push_back(i); } for (int j = 0; j < primes.size() && primes[j] <= x / i; j++) { st[i * primes[j]] = true; if (i % primes[j] == 0) break; } } return primes; } int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } void dfs(int u, int p, const vector<PII>& factor, vector<int>& divider) { if (u >= factor.size()) { divider.push_back(p); return; } int power = factor[u].second; int factorVal = factor[u].first; for (int i = 0; i <= power; i++) { dfs(u + 1, p, factor, divider); p *= factorVal; } } int main() { vector<int> primes = get_primes(N); int t; scanf("%d", &t); while (t--) { int a0, a1, b0, b1; scanf("%d %d %d %d", &a0, &a1, &b0, &b1); } return 0; }

#include <iostream> #include <algorithm> #include <vector> using namespace std; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int lcm(int a, int b) { return a / gcd(a, b) * b; } int solve(int a0, int a1, int b0, int b1) { int ans = 0; // 枚举b1的所有约数 for (int x = 1; x * x <= b1; x) { if (b1 % x == 0) { // 检查x是否满足条件 if (gcd(x, a0) == a1 && lcm(x, b0) == b1) { ans; } // 检查对应的另一个约数 int y = b1 / x; if (x != y && gcd(y, a0) == a1 && lcm(y, b0) == b1) { ans++; } } } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); }

#pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #include <cstdio> #include <vector> #include <algorithm> using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 45000; vector<int> get_primes(int x) { vector<int> primes; vector<bool> st(x + 1); for (int i = 2; i <= x; i++) { if (!st[i]) { primes.push_back(i); } for (int j = 0; j < primes.size() && primes[j] <= x / i; j++) { st[i * primes[j]] = true; if (i % primes[j] == 0) break; } } return primes; } int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } void dfs(int u, int p, const vector<PII>& factor, vector<int>& divider) { if (u >= factor.size()) { divider.push_back(p); return; } int power = factor[u].second; int factorVal = factor[u].first; for (int i = 0; i <= power; i++) { dfs(u + 1, p, factor, divider); p *= factorVal; } } int main() { vector<int> primes = get_primes(N); int t; scanf("%d", &t); while (t--) { int a0, a1, b0, b1; scanf("%d %d %d %d", &a0, &a1, &b0, &b1); } return 0; }