#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 你的点赞和关注就是我更新题解的最大动力！ 点个赞吧 ↓ ！

远古时期代码忘了lcm（）

题目大意 求出一个正整数 xxx 满足 gcd(x,a0)=a1\tt{gcd(x,a_0)=a_1}gcd(x,a0 )=a1 且 lcm(x,b0)=b1\tt{lcm(x,b_0)=b_1}lcm(x,b0 )=b1 。 解题思路 首先想到的是直接枚举 xxx，如果满足要求则累加答案，因为 x>b1x>b_1x>b1 一定不满足 lcm(x,b0)=b1\tt{lcm(x,b_0)=b_1}lcm(x,b0 )=b1 ，所以 xxx 从 111 一直枚举到 b1b1b1。代码如下： 时间复杂度 O(n⋅b1)O(n\cdot b_1)O(n⋅b1 )，只适用于 50%50\%50% 的数据，需要再优化。 优化思路 因为 lcm(x,b0)=b1\tt{lcm(x,b_0)=b_1}lcm(x,b0 )=b1 的前提条件是 x∣b1x\mid b_1x∣b1 ，即 xxx 是 b1b_1b1 的因数，枚举 b1b_1b1 的因数的时间复杂度是 O(b1)O(\sqrt{b_1})O(b1 )，再判断是否满足 gcd(x,a0)=a1\tt{gcd(x,a_0)=a_1}gcd(x,a0 )=a1 和 lcm(x,b0)=b1\tt{lcm(x,b_0)=b_1}lcm(x,b0 )=b1 的条件即可，时间复杂度 O(n⋅b1)O(n\cdot\sqrt{b_1})O(n⋅b1 )。 参考代码

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

#include <bits/stdc++.h> #define inf 1000000000 #define N 50000 #define ll long long using namespace std; int read(void) { int x = 0,f = 1;char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') { f = -1; } ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } int n,tot; int a0,b0,a1,b1,ans; int pri[50005]; bool mark[50005]; void getpri(void) { for (int i = 2;i <= N;i++) { if (!mark[i]) { pri[tot] = i; } for(int j=1;j<=tot&&pri[j]*i<=N;j) { mark[pri[j] * i] = 1; if (pri[j] % i == 0) { break; } } } } void solve(int x) { int c0 = 0,c1 = 0,c2 = 0,c3 = 0; while (a0 % x == 0) { a0 /= x; c0++; } while (a1 % x == 0) { a1 /= x; c1++; } while (b0 % x == 0) { b0 /= x; c2++; } while (b1 % x == 0) { b1 /= x; c3++; } if (c0 == c1 && c2 == c3) { if (c1 <= c3) { ans *= c3 - c1 + 1; } else { ans = 0; } } else if (c0 != c1 && c2 != c3 && c1 != c3) { ans = 0; } } int main(void) { getpri(); n = read(); while(n--) { ans = 1; a0 = read(); a1 = read(); b0 = read(); b1 = read(); for (int i = 1;i <= tot;i++) { solve(pri[i]); } if(b1 != 1) { solve(b1); } printf("%d\n",ans); } 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 <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; }