Legendre公式

 参考：Legendre公式：数论罪恶的开始 - 知乎

Legendre公式和Kummer定理 - tkandi - 博客园    

Legendre公式:

 

 

解释：n是一个正整数，p是一个小于等于n的质数

输出：通过Legendre公式可得到 n! 的其中一个质数 p 的幂次

 

 

Legendre公式p - 进制形式:

与上式等价

 

例题：小苯的因子查询_牛客题霸_牛客网

解：

2是质数，通过legendre公式求解

查看代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
const int N = 1e6 + 5;int binpow(int a, int b){if(b == 0) return 1;int res = 1;while(b){if(b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}void solve(){int n;cin >> n;int k = 0;//legendre公式while(n){k += n / 2;n /= 2;}cout << binpow(k + 1, mod - 2) % mod << " ";return ;
}