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（）

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

话不多说，请看题解~

因为我们的lcm(b0,x)=b1lcm(b0,x)=b1lcm(b0,x)=b1 所以xxx一定是b1b1b1的因数 因此我们只要用一个循环遍历xxx就可以过了 时间复杂度O(tb1)O(t\sqrt{b1})O(tb1 ) 极限复杂度为2000∗2000000000≈894427192000*\sqrt{2000000000}\approx894427192000∗2000000000 ≈89442719可过 代码 制作不易,求点赞

代码如下

#include<bits/stdc++.h> using namespace std; int n,a0,a1,b0,b1; int gcd(int x,int y){return y?gcd(y,x%y):x;} int lcm(int x,int y){return x/gcd(x,y)y;} int main(){ cin>>n; while(n--){ int cnt=0; cin>>a0>>a1>>b0>>b1; for(int x=1;xx<=b1;x++){ if(b1%x==0){ if(gcd(x,a0)==a1 && lcm(x,b0)==b1) cnt++; if(x*x!=b1) if(gcd(b1/x,a0)==a1 && lcm(b1/x,b0)==b1) cnt++; } } cout<<cnt<<endl; } return 0; }

这题太神圣了，你猜为什么非要说他的爸爸是“BT” #include <bits/stdc++.h> /* #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <set> #include <ctime> #include <queue> #include <cmath> #include <vector> #include <algorithm> #include <map> */ #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; }