好题,用到唯一分解定理的推广。题意:给一个整数n(1 <= n <= 10^9),求满足等式1/x + 1/y = 1/n(x,y,n都是正整数且x <= y)的解一共有多少组。
我的解题思路:因为x和y都是正整数,所以1/x和1/y都大于1,所以1/x和1/y都小于1/n,可知x和y都会大于n。那么假设x = n + a,y = n + b,这样的话将等式化为xy = n(x+y)后再代入化简就得到n^2 = ab,这样就是求a和b有多少种组合了,说白了,就是求n^2的因数个数。求一个正整数的因数个数可以用到唯一分解定理的推广,将一个正整数N分解成素因数的乘积p1^a1 * p2^a2 * ... * pn^an,它的因子个数为(1+a1)(1+a2)...(1+an)。注意:由于n的范围比较大,所以我们不能直接将n^2分解,我们可以通过分解n从而得知n^2分解的情况,由此计算答案。
我的解题代码:
#include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cmath> #include <algorithm> using namespace std; typedef long long Long; const int N = 50000; bool isprime[N]; int primes[N], pn; Long ans, n; void InitRead(); void DataProcess(); void FastSieve(int maxn); void Factor(Long x); int main() { int t; scanf("%d", &t); InitRead(); while (t--) { DataProcess(); } return 0; } void InitRead() { memset(isprime, true, sizeof(isprime)); isprime[0] = isprime[1] = false; pn = 0; FastSieve(N); return; } void DataProcess() { static int tn = 1; scanf("%lld", &n); Factor(n); printf("Scenario #%d:\n%lld\n\n", tn++, (ans+1) >> 1); return; } void FastSieve(int maxn) { for (int i=2; i<=maxn; ++i) { if (isprime[i]) primes[pn++] = i; for (int j=0; j<pn; ++j) { if (i * primes[j] > maxn) break; isprime[i * primes[j]] = false; if (i % primes[j] == 0) break; } } return; } void Factor(Long x) { ans = 1; Long cnt = (Long)sqrt(x + 0.5); for (Long i=0; i<pn; ++i) { if (primes[i] > cnt) break; if (x % primes[i] == 0) { Long temp = 0; while (x % primes[i] == 0) { x /= primes[i]; temp++; } ans *= 1 + temp * 2; //分解n但是计算n^2的情况 } } if (x > 1) ans *= 3; //分解n但是计算n^2的情况 return; }