P1082 [NOIP2012 提高组] 同余方程欧拉定理

2024-07-26 15:18 由尔一发表于 #其他

[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

提示

数据规模与约定

对于 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;
}