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

鸽巢原理:

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注