信息蒟蒻对提高组的一个月妄想（1）之初等数论
裴属定理{
a=mk,b=nk
(m,n)=1
xm+yn=1
}
乘法逆元：https://blog.csdn.net/weixin_43828245/article/details/102753727（好歹看的懂定义。。。
哦，还有https://blog.csdn.net/qq_43791377/article/details/89809193
{求法：费马小定理
exgcd
递推
}
埃式筛 https://blog.csdn.net/holly_Z_P_F/article/details/85063174（即按倍数筛（代码中i*2可改为i*i)
线性筛（欧拉筛（欧拉我恨你）也是找到一个数然后筛它倍数，但是欧拉筛可以做到不重复https://blog.csdn.net/weixin_45691703/article/details/128569209
注意！：gcd为最大公约数，lcm为最小公倍数（很显然，我脑子不太好使，记不住）。。。
{高精度适宜更相减损法{
gcd(a,b)=gcd(b,a-b)=gcd(a,a-b)
gcd(2a,2b)=2gcd(b,a mod b)
}
代码更加简单的欧几里得算法{
gcd(a,b)=gcd(b,a mod b)
}
}
欧拉函数（欧拉我有恨你了）phi(m)就是中与互素的数的个数
n=pow(p1,c1)*pow(p2,c2)*...*pow(pm,cm)
则phi(n)=𝜑(𝑁) = N ∗ ς质数p|N(1 − 1/𝑝)
欧拉函数性质
1~N中与N互质的数之和为N∗𝜑(𝑁)/2
若a,b互质，则𝜑(𝑎𝑏) = 𝜑(a)𝜑(b) （积性函数）
若p|n且pow(p,2)|n，则𝜑 𝑛 = 𝜑 𝑛/𝑝 ∗ 𝑝
若p|n且pow(𝑝,2)∤ 𝑛，则𝜑 𝑛 = 𝜑 𝑛/𝑝 ∗ (𝑝 − 1)
σ𝑑|𝑛 𝜑 𝑑 = 𝑛 （狄利克雷卷积)
*积性函数
如果当a,b互质时，有f(𝑎𝑏) = f(a)f(b)，则称f为积性函数
若f是积性函数，且N = 𝑝1𝑐1𝑝2𝑐2 … 𝑝𝑚𝑐𝑚，则f(N) = σ𝑖=1 𝑚 𝑓(pici)
...
好吧我数学知识有限谢谢
同余里面一个数上面一个横杠代表模m余这个数的同余类，0到m-1打横杠就叫完全剩余系
在完全剩余系中互质的即为简化剩余系，简化剩余系关于模m乘法封闭
欧拉的又双叒叕定理等{
费马小定理：pow(a,p) = a(mod p),即pow(a,p-1)=1(mod p)
欧拉定理：当(a,n)=1 ,pow(a,phi(n))=1(mod n)
当p是质数时，phi(p)=p-1,pow(a,p)=(这个是等号)pow(a,phi(p)+1)=a(mod p)
推论：若(a,n)=1,对于任意正整数b,pow(a,b)=pow(a,b mod phi(n))(mod n)
多少有点似懂非懂吧，氦
拓展欧几里得算法（差点忘了，欧几里得算法上面有）：
int exgcd(int a,int b,int &x,int &y){
if(!b){ x=1;y=0;return a;}
int d=exgcd(a,b,x,y);
int z=x;x=y;y=z-y*(a/b);
return d;
}
这玩意是给裴属定理，也就是a*x+b*y=gcd(a,b)一组解
如果遇到普通的a*x+b*y=c，我们可以用上述特殊解找通解
线性同余方程：
a*x=b(mod m),求x
若成立，则y*m=b-a*x（其实是为了后面推算，正常好理解版本为a*x=y*m+b)
我们的推算版：a*x+m*y=b
裴属定理又来力，将原式代入a*x+b*y=c,如果有解，gcd(a,m)|b
然后先找到a*x0+m*y0=gcd(a,m)
然后x=x0*b/gcd(a,m)，即一个可爱的可背性公式
中国剩余定理
好，先插播一段抽象的文言文（说真的，我觉得迪利克雷卷积更抽象）
今有物，不知其数，三三数之，剩二；五五数之，剩三；七七数之，剩二。问物几何？
好了，从前有m1,m2...至mn,它们两两互质
然后有个m,等于它们全加起来
还有个Mi，等于m/mi
然后是个ti,Mi*ti=1(mod mi)
对于任意正整数a1,a2...an
有一个{
x=a1(mod m1)
x=a2(mod m2)
...
x=an(mod mn)
}
然后，根据孙子的中国剩余定理，可得x=a1*M1*t1+a2*M2*t2+...+an*Mn*tn（文本文档，不知到怎么打sigma见谅）
然而，中国剩余定理只给了个解，最小还得对m取模。。。
Sumdiv(poj1845)
分解A
得到A的B次方的质因数分解式（我能看的懂就行捏
约数和是就那个公式
然后等比数列求和
(a+b)%m=(a%m+b%m)%m
(a*b)%m=(a%m*b%m)%m
a/b%m=a%(b*m)/b
一些同余的式子
虽然不太懂但是貌似有点用
哦，逆元的线性打表递推法
递推公式：inv[i]=(p-p/i)*inv[p%i]%p)
当pi-1不是9901倍数时，求出起模9901的乘法逆元
如果是，就为B*ci+1 (mod 9901)
https://blog.csdn.net/weixin_34064653/article/details/93960412
Prime Distance(poj2689)
这道题主要来讲就是先筛出sqrt(2e9),也就是大约50000以内的素数
然后所有合数都一定有这以内的质因子
其实剩时间还可以只筛sqrt(r)
然后再拿这些数去筛l至r
然而很显然你不可能筛50000*1000000，毕竟2开始就没了一半了。。。
然后就只剩质数了
一个p[1000001]的数组
true为质数 false为合数
https://tool.4xseo.com/a/8447.html
阶乘分解
给定正整数N(N≤10^6)，把n!分解质因数，输出出对应的pi和ci
先筛出N以内质数
然后设质数P，它的指数为[n/p]+[n/p^2]....（这玩意其实就是有一个p的搜一遍，两个p的搜一遍，但两个在一个中也搜了一遍，所以不需要乘，直接再加一遍即可，后面同理）
当P大于根号N时
只可能有n/p
所以不会有可爱的TLE
https://blog.csdn.net/m0_51841071/article/details/116539396
余数求和（bzoj1257)
首先，通过思考，可得k mod i=k-[k/i]*i
其实还是经常没有往这方面想，后来发现这个式子几乎不思考即可得到，只是甚至没想过会使用
对于i<=sqrt(k)
每个商不一定连续但绝对不同，这时i比商的跨度小，因此枚举i
对于i>=sqrt(k)
每个商连续且可能有多个，这时i比商的跨度大，因此枚举商
运用整除以及等差数列求和算出这部分的余数
https://blog.csdn.net/giftedpanda/article/details/99844152
Hankson的趣味题（Noip2009)
就一定程度上而言，这道题有点暴力
不论d再大
2e9以内它的因数都可以枚举
而2e9以内整数约数之多几千个，因此不会TLE
https://www.sohu.com/a/162622104_99893619
Visible Lattice Points(poj3090）
首先除去特殊的（1，0）和（0，1）
如果gcd(x,y)!=1
那么它前面一定有经历过点(x/gcd(x,y),y/gcd(x,y))
而想要找一个数及与它互质有多少，phi来了
由于对称所以乘二还有原点
https://blog.csdn.net/weixin_43874261/article/details/88373682
The Luckist Number(poj3696)
L个8等于8乘L个1等于9分之一的8乘L个9
因此若9*L|8*(pow(10,x)-1)
d=gcd(L,8)
9*L/d|pow(10,x)-1
pow(10,x)=1(mod 9*L/d)
然后根据我也记不得的定理可知：
若(a,n)=1
使pow(a,x)=1(mod n)的最小的正整数x为phi(n)的约数
接着就是x最小为一个phi(9*L/d)的约束，然后，枚举大法万岁！
同余方程(NOIP2012)
根据线性同余方程的知识点，通过套公式可得a*x+b*y=1
exgcd得出a*x0+b*y0=gcd(a,b)的解
接着将其代入公式
x=(x0%b+b)%b
https://www.cnblogs.com/CXCXCXC/p/4752391.html
Strang Way to Express Integers(poj2891)
这道题并没有说mi之间两两互质，所以得用exgcd
由于它有n个方程，首先，设前k-1个方程
此时的m等于m1+m2...+mk-1
而此时，x+tm为前k-1个方程的解
这玩意的成因：对于第k个方程，有x+tm=ak(mod mk),因此，由于题目会成立，所以必定有一个x+tm是前k-1个方程的解
接着，在n次的exgcd后，我们蹭啊蹭，蹭到了最后的解
https://codeleading.com/article/97291181151/
