extended euclidean algorithm

拓展欧几里得算法

定义

为了介绍扩展欧几里得，我们先介绍一下贝祖定理：
即如果a、b是整数，那么一定存在整数x、y使得ax+by=gcd(a,b)。
换句话说，如果ax+by=m有解，那么m一定是gcd(a,b)的若干倍。（可以来判断一个这样的式子有没有解）
有一个直接的应用就是 如果ax+by=1有解，那么gcd(a,b)=1；

但是，对于上面的式子ax+by=m来说，我们并不仅仅想要知道有没有解，而是想要知道在有解的情况下这个解到底是多少。
所以，扩展欧几里得算法就可以使用了，当到达递归边界的时候，b==0，a=gcd(a,b) 这时可以观察出来这个式子的一个解：a1+b0=gcd(a,b)，x=1,y=0，注意这时的a和b已经不是最开始的那个a和b了，所以我们如果想要求出解x和y，就要回到最开始的模样。

算法

拓展欧几里得算法(求出满足ax+by=G的整数x与y[x为满足条件的最小正整数]),返回值为G(正常为gcd(a,b))

ll ex_gcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    ll d = ex_gcd(b, a % b, x, y);
    ll temp = y;
    y = x - a / b * y;
    x = temp;
    return d;
} 

模板题

【模板】乘法逆元

【模板】乘法逆元

题目背景

这是一道模板题

题目描述

给定 $n,p$ 求 $1\sim n$ 中所有整数在模 $p$ 意义下的乘法逆元。

这里 $a$ 模 $p$ 的乘法逆元定义为 $ax\equiv1\pmod p$ 的解。

输入格式

一行两个正整数 $n,p$。

输出格式

输出 $n$ 行，第 $i$ 行表示 $i$ 在模 $p$ 下的乘法逆元。

样例 #1

样例输入 #1

10 13

样例输出 #1

1
7
9
10
8
11
2
5
3
4

提示

$ 1 \leq n \leq 3 \times 10 ^ 6, n < p < 20000528 $

输入保证 $ p $ 为质数。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define M 100007
#define N 1007
#define INF 0x3f3f3f3f
#define ll long long
#define db double
ll a, p;
void ex_gcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1, y = 0;
        return;
    }
    ex_gcd(b, a % b, x, y);
    ll temp = y;
    y = x - a / b * y;
    x = temp;
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin >> a >> p;
    ll x, y;
    for (int i = 1; i <= a; i++) {
        ex_gcd(i, p, x, y);
        cout << (x % p + p) % p << endl;
    }
    return 0;
}  // ax+py=1

#include<cstdio>
#define ll long long
using namespace std;
ll inv[3000007];
int main(){
   ll n,p;
   inv[1]=1;
   scanf("%lld%lld",&n,&p);
   printf("1\n");
   for(int i=2;i<=n;i++){
       inv[i]=(ll)p-(p/i)*inv[p%i]%p;
       printf("%lld\n",inv[i]);
   }
   return 0;
}