鸽巢原理+扩展欧几里得+欧拉筛

鸽巢原理：

转自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