solution 1:
费马小定理
若 p 为素数, a 为正整数, 且 a,p 互质, 则有 a^(p - 1)≡ 1(mod p)
那么 a 的逆元就是 a^(p - 2)
用一个快速幂即可
- //t 两个点
- #include<cstdio>
- using namespace std;
- #define int long long
- int p;
- int quickpow(int n,int k) {
- int ans = 1;
- while(k) {
- if(k & 1)
- ans = ans * n % p;
- n = n * n % p;
- k>>= 1;
- }
- return ans % p;
- }
- main() {
- int n;
- scanf("%lld%lld",&n,&p);
- for(int i = 1; i <= n; i++)
- printf("%lld\n",quickpow(i,p - 2));
- return 0;
- }
- solution 2:
- exgcd
- a * x = 1(mod p)
则 a * x + p * y = 1
- //t 一个点
- #include<cstdio>
- using namespace std;
- int x,y;
- void exgcd(int a,int b) {
- if(b == 0) {
- x = 1;
- y = 0;
- return ;
- }
- exgcd(b,a % b);
- int tmp = x;
- x = y;
- y = tmp - a / b * y;
- }
- int main() {
- int n,p;
- scanf("%d%d",&n,&p);
- for(int i = 1; i <= n; i++) {
- exgcd(i,p);
- printf("%d\n",(x % p + p)% p);
- }
- return 0;
- }
- solution 3:
线性递推
根据费马小定理的公式进行推导得出
- #include<cstdio>
- using namespace std;
- #define maxn 3000010
- #define ll long long
- ll inv[maxn];
- int main() {
- int n,p;
- scanf("%d%d",&n,&p);
- inv[1] = 1;
- printf("1\n");
- for(int i = 2; i <= n; i++) {
- inv[i] = (ll)(p - p / i) * inv[p % i] % p;
- printf("%lld\n",inv[i]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2934000.html