题目

给定$m$和%n%,并且$m,n$互质。
求$k,0 < k < n$

使得 $km \%n =1$

思路

法1

直接扩展欧几里得算法， 使用这算法的时候，可能会求出负数的答案。需要加$n$然后膜$n$

#include <iostream>
#include <cstdio>
using namespace std;
int exgcd(int a, int b, int &x, int &y){
    if(b == 0){
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main(){
    int m, n;  // a = m, b = n;
    int x, y;
    scanf("%d %d", &m, &n);
    exgcd(m, n, x, y);
    printf("%d", (x + n) % n);
    return 0;
}

法2

根据欧拉公式：$m$为正整数, $a$为整数, 且$(a, m) = 1$，则
$$ a^{\phi(m)} \% m = 1 $$
根据题意， 则$$m^{\phi(n)} \% n = 1$$
又，$$km \%n =1$$
所以：$$km \%n =m^{\phi(n)} \% n$$
$$k =m^{\phi(n) - 1} \% n$$

代码中在快速幂的时候，就直接取膜了。

#include <cstdio>

int quick_pow(int a, int b, int p){
    int ans = 1;
    while(b){
        if(b & 1){
            ans = (long long)ans * a % p;
        }
        a = (long long )a * a % p;
        b >>= 1;
    }
    return ans;
}
int phi(int x){ 
    int ans = x;
    for(int i = 2; i * i <= x; ++ i){
        if(x % i == 0){
            ans = ans / i * (i - 1);
        }
        while(x % i == 0){
            x /= i;
        }
    }
    if(x > 1){
        ans = ans / x * (x - 1);
    }
    return ans;
}
int main(){
    int m, n; 
    scanf("%d %d", &m, &n);
    int p = phi(n) - 1;
    int res = quick_pow(m, p, n);
    printf("%d\n", res);
    return 0;
}