【題目敘述】https://nanti.jisuanke.com/t/T2112
Python code (credit: Shawn Chen)
- 找出两个正整数 P, Q，使 P, Q 以 a 為最大公因數，以 b 為最小公倍數。2≤a <100000, 2≤ b ≤1000000。
- 依題意，
- P = a * p，Q = a * q，p 與 q 互質。
- b = a * p * q
- 令 c = b / a = p * q
- 從質數表 (prime[ ]) 中枚舉可以整除 c 的 p，共有 j 個數字。
- 滿足題意的 (P, Q) 個數為 2 ^ j。
# sqrt(1e6 / 2) < 1e3
maxn = 1000
p = [1 for i in range(maxn)]
prime = []
for i in range(2, maxn):
if p[i] == 1:
prime.append(i)
for j in range(i, maxn, i):
p[j] = 0
while True:
try:
a, b = map(int, input().split())
c = b / a
if c != int(c):
print(0)
break
j = 0
for i in prime:
if c % i == 0:
j += 1
print(2 ** j)
except:
break
C++ code (credit: Yui Huang)
- 利用質因數分解找出答案。
- 【例】GCD a = 3, LCM b = 60
- b / a = 20 = 2 ^ 2 * 5，共有2，5兩個不同的質因數。(cnt = 2)
- 由於 b / a 為兩個互質數字的乘積，(P, Q) 共有 2^cnt 種組合。
#include <bits/stdc++.h>
using namespace std;
int a, b, cnt;
int main(){
cin >> a >> b;
if (a > b || b % a){
cout << 0 << "\n";
return 0;
}
b /= a;
for (int i = 2; i <= b; i++){
if (b % i == 0){
while (b % i == 0){
b /= i;
}
cnt++;
}
}
cout << (1<<cnt) << "\n";
}
C++ code (credit: Amy Chou)
- (P, Q) 兩數，GCD為 x0，LCM為 y0。
- 令 P = p * x0, Q = q * x0，則 P * Q = p * q * x0 * x0 = x0 * y0。
- 因為 2≤x0<100000, 2≤y0≤1000000，x0 * y0 會超出int的範圍，因此所有變數都宣告成long long。
- 函式 gcd (x, y)：求 x, y 的最大公因數
- 令 N = x0 * y0，枚舉 P：範圍最小值為 x0，最大值為 sqrt (N)
- 依題意，N 要能被 P 整除。
- 依題意，N 與 N / P 的 GCD 為 x0。
- (P, N/P) 與 (N/P, P) 視為不同解。
#include <iostream>
using namespace std;
long long gcd(long long x, long long y) {
while ((x %= y) && (y %= x));
return x + y;
}
int main() {
long long x0, y0;
cin >> x0 >> y0;
if (x0 == y0) {
cout << "1\n";
} else {
long long N = x0 * y0;
long long ans = 0;
for (long long P = x0; P*P < N; P++){
if (N % P == 0 && gcd(P, N/P) == x0){
ans += 2;
}
}
cout << ans << "\n";
}
return 0;
}