一，单位元与逆元
（1）单位元：不影响运算的元素，如
加法单位元：0
乘法：1
逻辑与：1
逻辑或：0
矩阵乘法：单位矩阵（主对角线（左上到右下）上所有元素 = 1 其余位置元素 = 0）
（2）逆元：一个元素运算它的逆元=单位元
加法：a的逆元是-a a+(-a)=0
乘法：a的逆元是
a*
=1
不一定所有元素都有逆元
二，模运算下的加减乘运算与逆元求解
（1）模p的运算体系中的集合是？
{0，1，2，3，...，p-1}
可以理解为p,2p,-4p均通过该运算映射到了0
（2）加法逆元
有
所以逆元-a为p-a
（3）乘法逆元
暴力枚举范围
条件：两数成绩模p为1
如在mod 9系统中 2，5互为逆元
有费马小定理：
所以
(同余号两边同时乘
)
所以逆元
为
所以有快速幂解乘法逆元
ll qpow(ll a,ll b,ll mod){ ll ans=1; while(b){ if(b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans%mod; }（4）取余的a-b problem
a-b取余应为((a-b)%p+p)%p
解析：1，有公式如下
该式中第一个取余完后出现两种情况
一，获得负数，所以有+p后保证其大于等于1
二，获得正数，由于有+p干扰其结果所以有第二个%
（5）递推式求逆元
先说结论 首先inv[a]=
有inv[i]=(p-p/i)*inv[p%i]
推导如下
显然被除数等于商乘以除数加模数
（6）前缀积求逆元
pre[0]=1;//pre[]前缀积 for(int i=1;i<=n;i++) pre[i]=pre[i-1]*a[i]%p; invp[n]=qpow(pre[n],p-2); for(int i=n-1;i>=1;i--) invp[i]=invp[i+1]*a[i+1]%p;//invp[]前缀积的逆元 cout<<invp[x]*pre[x-1];//a[x]的逆元（7）逆元求组合数
首先看一下组合数
也就是说：
void init(int n){ fac[0]=inv[0]=1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%p; inv[n]=qpow(fac[n],p-2); for(int i=n-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%p; } ll c(ll n,ll m){ if(n<m) return 0; return fac[n]*inv[m]%p*inv[n-m]%p; }三，莫比乌斯函数
：如果x由k个不同的质数相乘得到，那么
，否则为0
例如：1001=7*11*13 所以
4=2*2 不是完全不同的 所以
四，欧拉函数
即为求1到n之间与n互质的数的个数
若gcd(a,b)=1则
且
五，欧拉定理与欧拉筛求逆元
如果a,p互质，有：
借此处声明：若a,p不互质，a无逆元
六，例题与解析
假设，约数个数
约数之和：
例题：
对于正整数 x，定义以下 88 个数论函数：
p(x)表示 x 的最小质因数。特别地，规定 p(1)=1
pnum(x) 表示 p(x) 在 x 的质因数分解中出现的次数，即满足 p(x)a∣x的最大非负整数 a。特别地，规定 pnum(1)=0
d(x)表示 x 的正约数个数。
μ(x) 表示莫比乌斯函数。规定 μ(1)=1；如果某个质数的平方整除 x，则 μ(x)=0；否则，若 x 含有 k 个不同的质因数，则
φ(x) 表示欧拉函数，即 1 到 x 中与 x 互质的整数个数。
sum(x) 表示 x 的所有正约数之和。
特别地，规定 pp(1)=1。
。特别地，规定 psum(1)=1
给定正整数 n 和 q 次查询。每次查询给出一个整数 x，请输出上述 8 个函数在 x 处的值。
代码如下：纯板子
#include<bits/stdc++.h> using namespace std; #define ll long long const int N=1e6+5; int n,q; int cnt,prime[N],d[N],p[N],pnum[N],mu[N],phi[N],pp[N],psum[N]; ll sum[N]; bool vis[N]; void Euler(int n){ vis[1]=mu[1]=phi[1]=sum[1]=d[1]=p[1]=pp[1]=psum[1]=1; for(int i=2;i<=n;i++){ if(!vis[i]){ prime[cnt++]=i; p[i]=i;pnum[i]=1;d[i]=2;mu[i]=-1;phi[i]=i-1;pp[i]=i;psum[i]=i+1;sum[i]=i+1; } for(int j=0;j<cnt&&i*prime[j]<=n;j++){ vis[i*prime[j]]=1; p[i*prime[j]]=prime[j]; if(i%prime[j]==0){//i与i*prime[j]拥有相同的最小质因数 prime[j] pnum[i*prime[j]]=pnum[i]+1;//质因子次数比i的多1 d[i*prime[j]]=d[i]/(pnum[i]+1)*(pnum[i]+2); mu[i*prime[j]]=0; phi[i*prime[j]]=phi[i]*prime[j]; pp[i*prime[j]]=pp[i]*prime[j]; psum[i*prime[j]]=psum[i]+pp[i*prime[j]]; sum[i*prime[j]]=sum[i]/psum[i]*psum[i*prime[j]]; break; } //i*prime[j]比i多出了新的最小质因数prime[j] pnum[i*prime[j]]=1; d[i*prime[j]]=d[i]*2; mu[i*prime[j]]=-mu[i]; phi[i*prime[j]]=phi[i]*(prime[j]-1); pp[i*prime[j]]=prime[j]; psum[i*prime[j]]=prime[j]+1; sum[i*prime[j]]=sum[i]*(prime[j]+1); } } } int main(){ scanf("%d%d",&n,&q); Euler(n); while(q--){ int x; scanf("%d",&x); printf("%d %d %d %d %d %lld %d %d\n",p[x],pnum[x],d[x],mu[x],phi[x],sum[x],pp[x],psum[x]); } }借这个题说一下对欧拉筛的理解
例题2：与素数有关的神秘序列加强版
小可获得了一个长度为n的序列1,2,..a1,a2,..an，这时他发现，假如他按照以下规则再构造一个长度为n的f序列，他就能够akioi了。规则如下：
对于x=1或x=素数的情况，fx=x
对于x≠1且x≠素数的情况，p是x的最小质因子，fx=fp+gcd(x,ax)。
当然了，对序列f有很多次询问哦。
代码如下直接模拟即可，重点在欧拉筛
#include<bits/stdc++.h> using namespace std; const int N=3e6+5; int a[N],f[N],prime[N],vis[N],cnt; void Euler(int n){ vis[1]=f[1]=1; for(int i=2;i<=n;i++){ if(!vis[i]){ prime[cnt++]=i; f[i]=i; } for(int j=0;j<cnt&&i*prime[j]<=n;j++){ vis[i*prime[j]]=1; f[i*prime[j]]=f[prime[j]]+__gcd(i*prime[j],a[i*prime[j]]); if(i%prime[j]==0){//i与i*prime[j]拥有相同的最小质因数 prime[j] break; } //欧拉筛会把所有的合数拆分成i*prime[j] //break保证prime[j]一定是最小质因数或者说所有的合数将被其最小质因数标记vis[i*prime[j]]=1 //若j继续++则i*prime[j]的最小质因数将不再是prime[j] //举例i=18 prime[j]=2 此时i*prime[j]=36,36被最小质因数2标记合数 //若j++，prime[j]=3 此时i*prime[j]=54,54被非最小质因数3标记合数 //后续当i=27时54将被重复标记，时间复杂度增大 /*即i当可以拆分成prime[j]*x的形式时（i%prime[j]==0），其显然拥有最小质因数prime[j] 若j++，i*prime[j+1]=x*prime[j]*prime[j+1]显然拥有prime[j]这个更小的质因数，却仍被prime[j+1]这个更大的质因数标记 */ } } } int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } Euler(n); int T,x; scanf("%d",&T); while(T--){ scanf("%d",&x); printf("%d\n",f[x]); } }今天就这样吧，明天还有，早休息同学们
