4 条题解
-
1
# include <bits/stdc++.h> using namespace std; long long gcd(long long a, long long b) { if (b == 0) { return a; } else { return gcd(max(a % b, b), min(a % b, b)); } } int main() { int P, Q; cin >> P >> Q; int ret = 0; for (int i = P; i <= Q; i++) { if ((P * Q) % i == 0 && gcd(i, (P * Q) / i) == P) { ret++; } } printf("%d", ret); return 0; }
-
1
#include<iostream> #include<cmath> using namespace std; typedef long long ll; int m,n,ans,flag; ll gcd(ll x,ll y) { if(y==0) {return x;} return gcd(y,x%y); } int main() { cin>>n>>m; for(int i=1;i<=sqrt(1ll*m*n);i++) { if((1ll*n*m)%i==0&&gcd(i,(1ll*n*m)/i)==n) { ans++; if(1ll*i*i==1ll*n*m) flag=1; } } cout<<ans*2-flag;//最后乘以二是因为只遍历了一半 return 0; }
-
0
由于 ,我们有,所以在此基础上,找出所有乘积为且最大公约数为的即可。
令,由于,所以显然互质,这启发我们枚举所有互质的即可。因为,所以,枚举的所有约数即可。时间复杂度为。相应地,这也告诉我们当无法被整除时,题目无解。
最后注意一点, 时要特判,输出。
#include <iostream> #include <cmath> using namespace std; int x, y, t; long long ans; int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); cin >> x >> y; if (x > y) swap(x, y); if (y % x != 0) { cout << 0 << endl; return 0; } t = y / x; if (t == 1) { cout << 1 << endl; return 0; } for (int i = 1; i * i < t; ++i) if (t % i == 0 && gcd(t / i, i) == 1) ++ans; ans *= 2; cout << ans << endl; return 0; }
-
0
include <bits/stdc++.h>
using namespace std; long long gcd(long long a, long long b) { if (b == 0) { return a; } else { return gcd(max(a % b, b), min(a % b, b)); } } int main() { int P, Q; cin >> P >> Q; int ret = 0; for (int i = P; i <= Q; i++) { if ((P * Q) % i == 0 && gcd(i, (P * Q) / i) == P) { ret++; } } printf("%d", ret); return 0; }
- 1
信息
- ID
- 30
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 2
- 标签
- 递交数
- 49
- 已通过
- 21
- 上传者