- 强烈推荐：大佬的博客：数论算法详解，超详细
一.欧几里得算法
二.扩展欧几里得算法
- 1.扩展欧几里得
- 扩展欧几里得原理
- 定理
- （1）.扩展欧几里得算法应用
- （2）例题1.求整数 $x$ 和 $y$ 使得 $a x + b y = 1$
- （3）例题2.扩展欧几里得模板
二.费马小定理

强烈推荐：大佬的博客：数论算法详解，超详细

链接：
https://www.zhihu.com/question/379824357/answer/1088257294

一.欧几里得算法

辗转相除法，又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。

int gcd(int a, int b)
{if(b == 0) return a;return gcd(b, a%b);
}

有不懂的或者想了解更多的可以点击下方链接
详解及其拓展应用链接

二.扩展欧几里得算法

1.扩展欧几里得

扩展欧几里得算法：对于整数 $a$ ， $b$ ，必定存在整数对 $x$ ， $y$ 满足
$a x + b y = g c d (a, b)$

扩展欧几里得原理

要求 $a x + b y = g c d$ 的整数解 $x, y,$ 假设已经求得了 $b x^{'} + (a$ 的整数解 $x^{'}$ 和 $y^{'}$ ，再将 $a$ 带入，有 $a y^{'} + b (x^{'} - (a / b) * y^{'}) = g c d ，$ 于是我们就得到了 $(x, y)$ 和 $(x^{'}, y^{'})$ 之间的关系: $x = y^{'}, y = x^{'} - (a / b) * y^{'}$ 。而当 $b = 0$ 时， $g c d = a ，$ 此时有 $x = 1, y = 0 .$ 通过类似于辗转相除法的递归过程，不断地迭代，可得到 $a x + b y = g c d$ 的一个正整数解，我们可将它称为特解，同时得到 $g c d$ 的值。

定理

定理1： $gcd(a,b)==gcd(b,a%b)gcd(a,b)==gcd(b,a\%b)$ 这个是欧几里得提出并证明的。 ( $%\%$ 是取余的意思，在数学中可用 $m o d$ 表示)；

定理2: $a * x + b * y = = g c d (a, b)$ 一定存在解。这个定理又叫裴蜀定理，或贝祖定理。

（1）.扩展欧几里得算法应用

1.不定方程 $a x + b y = c$ 无解判定：如果 $c d = = 0$ 有解，否则无解
2.求解不定方程 $a x + b y = c ：$ 先用扩欧求出 $a x ’ + b y ’ = d = g c d (a, b)$ 的一组解 $x^{'}$ 和 $y^{'} ，$ 则方程原来的一组解为 $x = x^{'} c / d ， y = y^{'} c / d$ ，通解为 $x = x^{'} c / d + k b / d$ ， $y = y^{'} c / d - k a / d$ （ $k$ 为任意整数）
3.解模线性方程： $a \equiv b (m o d n)$ 的含义是a和b关于模n同余，即 $a m o d n = = b m o d n$ ，则 $a x - b = n y,$ 移项得 $a x - n y = b,$ 这恰好是一个二元一次不定方程，用2解决。
4.乘法逆元： $a x \equiv 1 (m o d n)$ 的解x称为 $a$ 关于模n的乘法逆元。若 $g c d (a, n) = 1$ 有唯一解，反之无解。注意：通过扩欧算出的不定方程有很多解，最终的逆元应该是 $（x%n+n）%n,（x\%n+n）\%n,$ 也就是逆元的范围是 $[0, n - 1]$
5.改写算式： $(a / b) m o d p = = (a (b 的逆元))$

详解+代码

（2）例题1.求整数 $x$ 和 $y$ 使得 $a x + b y = 1$

问题描述：求整数x和y使得 $a x + b y = 1$
限制条件： $1≤a,b≤10^9$
分析：如果 $g c d (a, b) \neq = 1$ ，显然无解（有公约数一除就不是整数了），反之，如果 $g c d (a, b) = 1,$ 就可以通过扩展辗转相除法来求解。事实上一定存在整数对 $(x, y)$ 使得 $a x + b y = g c d (a, b) ，$ 并可以用同样的算法求得。

int exgcd(int a, int b, int &x, int &y)
{int d=a;if (b != 0){d=exgcd(b, a%b, y, x);y-=(a/b)*x;}else{x=1; y=0;}return d;
}

详细代码见下文

（3）例题2.扩展欧几里得模板

题意翻译
一条直线：Ax+By+C=0（AB不同时为0），找到任意一个点（在-5e18~5e18之间）让它的横纵坐标均为整数，或者确定没有这样的点。
输入：A，B，C
输出：该点坐标，没有就输出-1
输入输出样例
输入 #1

2 5 3

输出 #1

6 -3

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll maxn=1e5;
ll ex_gcb(ll a,ll b,ll &x1,ll &y1)
{ll x2,y2;if(!b){x1=1;y1=0;return a;}ll d=ex_gcb(b,a%b,x2,y2);x1=y2;y1=x2-a/b*y2;return d;
}
int main()
{ll a,b,c,x,y;scanf("%lld%lld%lld",&a,&b,&c);c=-c;ll d=ex_gcb(a,b,x,y);if(c%d){puts("-1");exit(0);}x=x*c/d;y=y*c/d;printf("%lld %lld\n",x,y);return 0;
}

二.费马小定理

定义：费马小定理（Fermat Theory）是数论中的一个重要定理，其内容为：假如p是质数，且Gcd(a,p)=1，那么 a(p-1) ≡1（mod p）。即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。
题目：给定一个方程式f(x)=5×13+13×5+kax，给定一个非负整数k，求能不能找到一个尽量小的非负整数a，使得上述方程式中的x任意取值，结果都能被65整除，如果有，输出a的值，否则输出no。
理解：65=13×5。要使f(x)是65的倍数，只需要f(x)是5和13的倍数即可。
1.若f(x)是13的倍数，则(5×13+13×5+kax )% 13 == 0，其中13×5显然是13的倍数，所以只需(5×13+kax )是13的倍数，即(5×12+ka )x是13的倍数。
如果x是13的倍数，则不用考虑。
如果x不是13的倍数，则x一定与13互素，由费马小定理得，x12%13= =1，则5×12%13= =5。因为要让任意x满足条件，则括号内必为13的倍数，有(ka+5)%13= =0，则ka%13= =8。
2.同理可得ka%5= =2。
据此，若k为5或13的倍数，a一定无解，否则，一定有解。

#include<stdio.h>
int main()
{int k;while(scanf("%d",&k)!=EOF){int i=1;if(k%5==0||k%13==0)printf("no\n");elsewhile(i){if(k*i%5==2&&k*i%13==8){printf("%d\n",i);break;}i++;}}return 0;
}