大佬的数论合集

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

链接：
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$a， $b$b，必定存在整数对 $x$x， $y$y满足
$ax+by=gcd(a,b)$ax+by=gcd(a,b)

扩展欧几里得原理

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

定理

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

定理2: $a\ast x+b\ast y==gcd(a,b)$a∗x+b∗y==gcd(a,b)一定存在解。这个定理又叫裴蜀定理，或贝祖定理。

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

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

详解+代码

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

问题描述：求整数x和y使得 $ax+by=1$ax+by=1
限制条件： $1\le a,b\le 10^9$1≤a,b≤109
分析：如果 $gcd(a,b)\ne 1$gcd(a,b)​=1，显然无解（有公约数一除就不是整数了），反之，如果 $gcd(a,b)=1,$gcd(a,b)=1,就可以通过扩展辗转相除法来求解。事实上一定存在整数对 $(x,y)$(x,y)使得 $ax+by=gcd(a,b)，$ax+by=gcd(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)=5x13+13x5+kax，给定一个非负整数k，求能不能找到一个尽量小的非负整数a，使得上述方程式中的x任意取值，结果都能被65整除，如果有，输出a的值，否则输出no。
理解：65=13×5。要使f(x)是65的倍数，只需要f(x)是5和13的倍数即可。
1.若f(x)是13的倍数，则(5x13+13x5+kax )% 13 == 0，其中13x5显然是13的倍数，所以只需(5x13+kax )是13的倍数，即(5x12+ka )x是13的倍数。
如果x是13的倍数，则不用考虑。
如果x不是13的倍数，则x一定与13互素，由费马小定理得，x12%13= =1，则5x12%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");
        else
            while(i)
            {
               if(k*i%5==2&&k*i%13==8)
                {
                    printf("%d\n",i);
                    break;
                }
                i++;
            }
    }
    return 0;
}

注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧