欧几里得算法
直接上代码
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
int a, b;
cin >> a >> b;
cout << gcd(a, b);
return 0;
}
欧几里得算法是经典的最常用的辗转相除法求最大公因数。
下面我们思考为何辗转相除是正确的。
假设$$g = gcd(a, b), a = mg, b=ng$$
显然，m与n互素（没有共同因数），通过辗转相除，我们得到新的a1，b1
不断取模辗转相除最终可以得到某个数变为了0，得到(g, 0)。
那为什么不会得到(2g,0)、(3g,0)呢？因为在辗转相除的过程中，最开始的系数m、n互素，所以后面每对系数都是互素的，若有不互素情况，说明g不是gcd(a,b)。（说的有点拗口，难理解可以通过更相减损进行推导模拟）
Eratosthenes素数筛
前置
1.若x是素数，那么kx(k>1)一定不是素数。
2.非素数N的因子可以分为两组[2,$ \sqrt{N} \(]和[\) \sqrt{N} $, N],每个N在[2, \(\sqrt{N}\)]的因子，一定能在[\(\sqrt{N}\), N/2]上找到对应因子。
3.\(\sum_{i=2}^n\frac1i=lnn+\gamma\)（欧拉常数）
筛法
根据第一条，筛法就是素数的倍数，而且对于某个素数x和他的倍数kx，如果\(kx < x^2\),那么kx一定被其他更小的素数筛掉过了
根据第二条，我们要得到[2, N]的素数表，我们只要在[2,\(\sqrt{N}\)]中用素数去筛掉非素数。
根据第三条，时间复杂度为\(O(\sqrt{N}lnN)\)
代码
for (int i = 2; i * i <= n; ++i)
{
if (!not_prime[i])
{
for (int j = i * i; j <= n; j += i)
not_prime[j] = 1;
}
}
扩展欧几里得算法
问题
求\(ax+by=gcd(a,b)\)的解(x,y)。
分析
我们知道\(gcd(a,b)=gcd(b,a\%b)\)，那么让我们考虑另一个方程：\(bx_1+(a\%b)y_1=gcd(b,a\%b)\)
若能得到x1和y1,那么通过等式和a%b=a-(a/b)*b我们也能得到
考虑辗转相除法的过程，一直进行下去会得到
\[ax_n+0y_n = gcd(a,0) = a \]一组解便是\(xn=1,yn=0\),反推回去得到一组(x,y)。
考虑其他解(m,n)
同除gcd(a,b)可以得到c=a/g,d=b/g,显然c、d互素。
\[c(m-x)+d(n-y)=0 \]由于cd互素，那么
\[m-x=kd,n-y=kc(k不定) \]其中k不定，我们枚举k，那么
\[(m,n)=(x+b/g*k,y+a/g*k) \]例题
洛谷 青蛙的约会
//青蛙约会
#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL k_gcd(LL a, LL b, LL &x, LL &y)
{
if (!b)
{
x = 1, y = 0;
return a;
}
LL d = k_gcd(b, a % b, y, x);
y -= x * (a / b);
return d;
}
int main()
{
LL x, y, m, n, l, a, b, c, t, k;
//(m - n)t + lk = y - x, find positive min t
cin >> x >> y >> m >> n >> l;
if (m - n < 0)
a = n - m, c = x - y;
else
a = m - n, c = y - x;
b = l;
LL g = k_gcd(a, b, t, k);
if (c % g)
cout << "Impossible";
else
{
t = t * (c / g);
cout << (t % (b / g) + b / g) % (b / g);
}
return 0;
}