阶乘的分解质因数

首先说一下分解质因数：

唯一分解定理：任何一个数都可以唯一分解为几个质数的幂次乘积。

const int maxn = 1e6+5; int p[maxn], c[maxn]; int cnt = 0; void divided(int n){ for(int i = 2; i * i <= n; i++){ if(n % i == 0){ p[++cnt] = i; c[cnt] = 0; while(n % i == 0) n /= i, c[cnt]++; } } if(n > 1) p[++cnt] = n, c[cnt] = 1; }

阶乘的因式分解：

求1~n之内的数，因子为2的个数，即是求n！这个数中因子为2的个数

int sum = 0;

while(n){

        sum += n/2;

        n /= 2;

}

ull fun(ull n, ull x){ ull res = 0; while(n){ res += n / x; n /= x; } return res; }

 

 

例题：codeforcesC. Primes and Multiplication

 

直接分解x，得到唯一分解，然后求每个因子在1~n中出现的次数（使用阶乘的因式分解），然后用快速幂求解。

#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; const ull mod = 1e9+7; const int maxn = 1e6+5; ull p[maxn], c[maxn]; int cnt = 0; void divided(ull n){ for(ull i = 2; i * i <= n; i++){ if(n % i == 0){ p[++cnt] = i; c[cnt] = 0; while(n % i == 0) n /= i, c[cnt]++; } } if(n > 1) p[++cnt] = n, c[cnt] = 1; } ull fun(ull n, ull x){ ull res = 0; while(n){ res += n / x; n /= x; } return res; } ull quick_mod(ull x, ull n){ ull res = 1; while(n > 0){ if(n & 1) res = res * x % mod; x = x * x % mod; n >>= 1; } return res; } int main() { ull x, n; scanf("%llu%llu", &x, &n); divided(x); ull ans = 1; for(int i = 1; i <= cnt; i++){ ull pp = p[i]; ull num = fun(n, pp); ans *= quick_mod(pp, num); //printf("%llu %llu\n", pp, num); ans %= mod; } printf("%llu\n", ans); return 0; }