P1082 [NOIP2012 提高组] 同余方程 欧拉定理
[NOIP2012 提高组] 同余方程
解法
在这个问题中,我们想要找到 𝑥 使得ax≡1(modb)。根据欧拉定理,ab互质,得a^φ(b) ≡1(modb)。
先用欧拉φ(b),再求快速幂
为了应用欧拉定理,我们需要确认 a 和 b 是互质的,即 gcd(a,b)=1。如果 a 和 b 不是互质的,那么同余方程 ax ≡ 1(modb) 就没有解。
假设 a 和 b 是互质的,根据欧拉定理,我们有:a^φ(b) ≡ 1(modb)
这是直接由欧拉定理给出的。这里,φ(b) 是小于或等于 b 且与b 互质的正整数的个数。
如果我们有 a^φ(b) ≡ 1(modb),那么我们可以将等式两边同时乘以 a^(−1)(a 在模 b 下的逆元):a^φ(b) ⋅a^(−1) ≡ 1⋅a^(−1) (modb)
由于 a^φ(b) ≡1(modb),我们可以简化等式:1⋅a^(−1) ≡ a^(−1) (modb)
这里 a^(−1) 就是 ax≡1(modb) 的解,因为:a⋅a^(−1) ≡1(modb)
所以,a^φ(b)≡1(modb) 实际上给出了 a 的逆元 a^(−1) 的存在性,而 a^(−1)就是 ax≡1(modb) 的解。
总结来说,欧拉定理直接告诉我们 a^φ(b)≡1(modb),而要得到 ax≡1(modb) 的解,我们只需要取 a^(φ(b)−1)作为 x,因为 a^(φ(b)−1)就是 a 的逆元。
题目描述
求关于 x 的同余方程 ax≡1(modb) 的最小正整数解。
输入格式
一行,包含两个整数 a,b,用一个空格隔开。
输出格式
一个整数 x0,即最小正整数解。输入数据保证一定有解。
样例 #1
样例输入 #1
3 10
样例输出 #1
7
提示
数据规模与约定
- 对于 40% 的数据,2 ≤b≤ 1,000
- 对于 60% 的数据,2 ≤b≤ 50,000,000;
- 对于 100% 的数据,2 ≤a, b≤ 2,000,000,000。
代码
#include<iostream>
#include<map>
#include<vector>
#include<deque>
#include<algorithm>
#include<unordered_map>
#include<set>
#include<string>
using namespace std;
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define mm(a, b) memset(a, b, sizeof(a))
#define ll long long
#define mp make_pair
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const int N = 1e6 + 10, mod = 1e9 + 7;
ll n;
ll a[N], dp[N];
unordered_map<int, int> primes;
ll gcd(ll a, ll b){
return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
return a / gcd(a, b) * b;
}
ll yuehe(ll x) {
primes.clear();
int k = x;
for (int i = 2; i <= x / i; i++)
while (x % i == 0)
{
x /= i;
primes[i]++;
}
if (x > 1) primes[x]++;
ll res = 1;
for (auto p : primes)
{
ll a = p.first, b = p.second;
ll t = 1;
while (b--) t = (t * a + 1) % mod;
res = res * t % mod;
}
return res - k;
}
ll phi(ll x) {
ll res = x;
for (ll i = 2; i * i <= x; i++) {
if (x % i == 0) {
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
}
if (x > 1) res = res / x * (x - 1);
return res;
}
ll qmi(ll a, ll b, ll p)
{
ll res = 1 % p;
while (b)
{
if (b & 1) res = res * a % p;
a = a * (ll)a % p;
b >>= 1;
}
return res;
}
void solve() {
ll a, b;
cin >> a >> b;
if (gcd(a, b) != 1) return;
ll p = phi(b);
ll x = qmi(a, p - 1, b);
cout << x;
}
int main() {
ios;
int t;
//cin >> t;
t = 1;
while (t--) solve();
return 0;
}