[POJ 2992] Divisors【欧拉筛】
Problem:
Time Limit: 1000MS | Memory Limit: 65536K |
Description
Input
Output
Sample Input
5 1 6 3 10 4
Sample Output
2 6 16
Source
Solution:
先用欧拉筛筛出 [2, 431] 上的素数,再将阶乘整体分解质因数(若逐个分解则会 TLE),套用因数个数公式即可。
【因数个数公式】
对一个大于 1 的正整数 n 分解质因数:
则 n 的因数个数 f(n) 满足:
Code: O(T(N+PlogN)), 其中P为素数个数 [168K, 954MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; const int UPRANGE = 431; int prm[UPRANGE >> 1], prmSize; bool isprm[UPRANGE + 2]; inline void initPrime(){ memset(isprm, 1, sizeof(isprm)); isprm[0] = isprm[1] = 0, prmSize = 0; for(register int i = 2; i <= UPRANGE; i++){ if(isprm[i]) prm[++prmSize] = i; for(register int j = 1; j <= prmSize && i * prm[j] <= UPRANGE; j++){ isprm[i * prm[j]] = 0; if(i % prm[j] == 0) break; } } } int n, k; int cntPrm[UPRANGE >> 1]; inline void cntAsFactorial(int x, int weight){ for(register int i = 1; i <= prmSize; i++){ int tmp = x; while(tmp) cntPrm[i] += weight * (tmp /= prm[i]); } // 1..x has [x/p] multipliers of p, [x/p^2] multipliers of p^2, etc. } int main(){ initPrime(); while(scanf("%d%d", &n, &k) != EOF){ if(k > (n >> 1)) k = n - k; long long ans = 1; memset(cntPrm, 0, sizeof(cntPrm)); cntAsFactorial(n, 1), cntAsFactorial(n - k, -1), cntAsFactorial(k, -1); for(register int i = 1; i <= prmSize; i++) ans *= cntPrm[i] + 1; printf("%lld\n", ans); } return 0; }
发表评论