阶乘的分解质因数

首先说一下分解质因数：

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

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; }

 

 

 

总结

以上是生活随笔为你收集整理的阶乘的分解质因数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。