逆元
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) 的最小正整数解。
输入输出格式
输入格式:
一行,包含两个正整数 a ,用一个空格隔开。
输出格式:
一个正整数 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; }
文章评论