#洛谷#C/C++P1082 同余方程 逆元（欧拉函数）/拓展欧几里得

逆元

a * b = 1 (mod p) 则a,b互为逆元

费马小定理

a ^(p-1)  = 1 (mod p)

p 为质数

->   a * a ^(p-2)  = 1 (mod p)

于是 a和a ^(p-2) 互为逆元

欧拉函数

定义：φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))…..(1-1/p(n))      p(1),p(2)…p(n)为x的所有质因数

表示 小于x的数中与x互质的数的数目

欧拉公式：a ^ φ(p)  =1 (mod p)

-> a * a ^ (φ(p)  -1)  =1 (mod p)

a与 a ^ (φ(p)  -1) 互为逆元

题目描述

求关于 $x$ 的同余方程 ax≡1(modb) 的最小正整数解。

输入输出格式

输入格式：

一行，包含两个正整数 $,b$ ，用一个空格隔开。

输出格式：

一个正整数 x0​ ，即最小正整数解。输入数据保证一定有解。

输入输出样例

输入样例#1：

3 10

输出样例#1：

7

关于本题

ax≡1(modb)

由欧拉函数 a * a ^ (φ(b)  -1)=1 (mod b)

即求a ^ φ(b-1) 即可

本人提供的题解

拓展欧几里得和欧拉函数两种解法

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;

typedef long long LL;

int a,b,x,y,d;

void ex_gcd(int& ,int& ,int ,int );
void ex_gcd_work();
int euler(int );
LL fast_pow(LL ,LL ,LL );
void euler_work();

int main() {
	cin >> a >> b;
	ex_gcd_work();
	euler_work();
}

void ex_gcd(int &x,int &y,int a,int b) {
	if(b == 0) {
		y = 0;
		x = 1;		
	}
	else {
		ex_gcd(y,x,b,a % b);
	    y -= x * (a / b);
	}
}
void ex_gcd_work() {
	ex_gcd(x,y,a,b);
	cout << (x + b) % b << endl;
}
int euler(int n) {
	int res = n;
	for(int i = 2;i * i <= n;++i) {
		if(n % i == 0) res = res / i * (i - 1); //公式  (i-1)/i == 1-1/i
		while(n % i == 0) n /= i;
	}
	if(n > 1) res = res / n * (n - 1); //最后只剩下 小于4的素数  或者n本身是素数
	return res;
}
LL fast_pow(LL a,LL b,LL MOD) {
	LL res = 1;
	while(b) {
		if(b & 1) res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res % MOD;
}
void euler_work() {
	int e = euler(b) - 1;
	cout << fast_pow(a,e,b) << endl;
}