鸽巢原理：
转自CSDN博客
链接：https://blog.csdn.net/guoyangfan_/article/details/102559097
扩展欧几里得
其实扩欧求最大公约数这个都晓得，比较重要的是扩欧的一些应用
比如求小正整数解，之前在好多题目中都遇到过，但是每次都要现查怎么写，在这正好梳理一下
求ax+by=c的最小正整数解
首先设g=gcd（a，b）
若c不是g的整数倍，那么是没有整数解的（还是没有解？忘了。。。）
首先通过扩欧求出ax+by=gcd（a，b）的一组解x、y
代码：
void exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return;
}
exgcd(b,a%b,x,y);
int tmp=y;
y=x-(a/b)*y;
x=tmp;
}然后令：
x0=x*（c/g）
y0=y*（c/g）
这样x0和y0就是ax+by=c的一组解了
如何求ax+by=c的通解呢？这里直接就给公式了
x1=x0+n*（b/g）
y1=y0- n*（a/g）
该公式即为ax+by=c的通解，通过调整n，即可得到最小正整数解（或不存在）
欧拉筛代码模板
老是用，老是忘
void euler(int n)
{
for(int i=2;i<=n;i++)
{
if(!p[i])
prime[++cnt]=i;
for(int j=1;j<=cnt;j++)
{
if(i*prime[j]>n)
{break;}
p[i*prime[j]]=1;
if(i%prime[j]==0)
{break;}
}
}
}123