鸽巢原理:
转自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