sjp大佬让我写同余那就只能硬着头皮按学长的ppt来写了，咕咕咕
数学符号
不想一个一个打了，凑合着看吧
快速幂
输入b，p，k的值，求b^p mod k的值。
方法一
直接反复平方，复杂度是(O(n))基本没戏会TLE的，不用看了
方法二
如果(a)自己乘一次就变成了(a^2),(a^2)再自乘一次就变成了(a^4).....乘(n)次就变成了(2^n)
我们将b分解成二进制看一下下
假设b=(11)，分解成二进制就是((1011)),从左到右这些 (1)分别代表十进制的 (8),(2),(1),也就是(a^b=a^8 imes a^2 imes a^1)这就是快速幂的原理
int quick_pow(int a, int b)
{
int ans = 1, base = a;
while(b > 0)
{
if(b & 1)//和b%2!=0一样的效果
ans *= base;//把ans乘上对应的a^(2^n)
base *= base;//base自乘
b >>= 1;//位运算，b右移一位，如101变成10（把最右边的1移掉了），10010变成1001。现在b在二进制下最后一位是刚刚的倒数第二位。
}
return ans;
}
同余
概念
若 (m | (a − b))，则称$ a (与) b (对模) m$ 同 余，记作$ a ≡ b (mod m)$
同余的性质
1.自反性：(a ≡ a)
2.对称性：若 (a ≡ b)，则$ b ≡ a(
3.传递性：若) a ≡ b(，)b ≡ c(，则) a ≡ c$
4.同余式相加：若 (a ≡ b)，(c ≡ d)，则 (a ± c ≡ b ± d)
5.同余式相乘：若 (a ≡ b)，(c ≡ d)，则 (ac ≡ bd)
6.同幂性：若(a ≡ b(mod m)) 则(a^n ≡ b^n(mod m))
7.若(a mod p=x) ,(a mod q= x),则 (p,q)互质，则 (a mod p*q =x)
证明：
略，太难打了...自行百度吧...咕咕咕
乘法逆元
概念：
若 (ap ≡ 1 (mod m))，则称 (a) 和 (p)在模 $m (意义下互为乘法逆
元。简称) a $是 (p) 的逆元或$ p$ 是$$ 的逆元。为了方便我们常把 (a)
的乘法逆元记做$ a^{-1}$ 。
}
因为 (a imes a^{-1} ≡ 1)，所以我们可以把$ a^{−1} (看作)frac{1}{a} $。但请注意在模意义下不存在除法操作。乘法逆元可能不存在。
来自谷歌的解释：
(a⋅a′≡1pmod p)
我们称a′是a在模p意义下的乘法逆元，记作(a^{-1})。
其用途和倒数类似，若要在模(p)意义下将(a)除以(b)，不能直接(a/b)，因为除法是不满足模运算的，此时我们需要转为乘法：(a⋅b^{-1})。
求逆元的方法
扩展欧几里得
假如(b=1),由于(gcd(a,b)=1),因此(a=x=1)
假如(b≠1)，不妨假设(a=kb+r),并且我们已经求出了(bx+ry=1)的一组解((x_0,y_0))
(bx_0+(a-kb)y_0=1)
(ax_1+by_1=1)
(bx_0+ay_0-kby_0=b(x_0-ky_0)+ay_0=ax_1+by_1)
(x_1=y_0)
(y_1=x_0-ky_0)
那么((x_1,y_1))就是(ax+by=1)的一组解，这不就是exgcd？
void exgcd(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1, y = 0;
return;
}
exgcd(b, a % b, y, x);
y -= a / b * x;
}
快速幂法(o(n*log(n)))
p是质数
根据费马小定理：
若 (p) 为质数， (a) 为正整数，且 (a) 、 (p) 互质，则 (a^{p-1} equiv 1 pmod p) 。
因 (ax equiv 1 pmod b)
所以 (ax equiv a^{b-1} pmod b)
所以 (x equiv a^{b-2} pmod b)
所以我们可以用快速幂来算出 (a^{p-2} pmod p)值，这个数就是它的逆元了
代码就是快速幂，不会的请点这里
递推法(o(n))
p必须是质数
设 (p=ki+j,j<i,1<i<p) ，再放到 (mod p) 意义下就会得到： (ki+j equiv 0 pmod p)
两边同时乘 (i^{-1},j^{-1}) （注意：(1^{-1} equiv 1 pmod p) ）
(kj^{-1}+i^{-1} equiv 0 pmod p) ；
(i^{-1} equiv -kj^{-1}+ pmod p) ；
(i^{-1} equiv -(frac{p}{i}) (p mod i)^{-1}) ；
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#define ll long long int
using namespace std;
const int maxn=999999999;
const int minn=-999999999;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
long long p,c[3000005];
int main()
{
long long n;
scanf("%lld%lld",&n,&p);
c[1]=1;
printf("1
");
for(register int i=2; i<=n; i++)
{
c[i]=(p-p/i)*c[p%i]%p;
printf("%lld
",c[i]);
}
return 0;
}
模板题目：
代码：
方法一：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#define ll long long int
using namespace std;
const int maxn=999999999;
const int minn=-999999999;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
long long p,c[3000005];
int main()
{
long long n;
scanf("%lld%lld",&n,&p);
c[1]=1;
printf("1
");
for(register int i=2; i<=n; i++)
{
c[i]=(p-p/i)*c[p%i]%p;
printf("%lld
",c[i]);
}
return 0;
}
方法二：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#define ll long long int
using namespace std;
const int maxn=999999999;
const int minn=-999999999;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
long long p;
long long quick_pow(long long x,long long y)
{
long long ans=1;
while(y!=0)
{
if(y&1)
{
ans=((ans%p)*(x%p))%p;
}
x=((x%p)*(x%p))%p;
y>>=1;
}
return ans;
}
int main()
{
long long n;
scanf("%lld%lld",&n,&p);
for( int i=1;i<=n;i++)
{
printf("%lld
",(quick_pow(i,p-2))%p);
}
return 0;
}