Butteruni Blog
0%

2023牛客暑期多校9 B 证明

发表于 更新于 分类于

B-Semi-Puzzle: Brain Storm_2023牛客暑期多校训练营9 (nowcoder.com)

题意：给定 ， ，求 ，使得 ， ，保证所给数据在 内有解

前置知识：拓展欧拉定理 扩展欧几里德

假设当前已经存在 ，由拓展欧拉定理可知

于是对于合法解 ，那么

此时可以将问题转化成寻找 ，使得 ，即

由扩展欧几里德可知，该等式有解的充要条件为 ，即 ，于是 的范围可以这样递归变小到 。

不难发现，当 时， 对于所有 都成立。

每次将下一层递归得到的 代回同余方程即可得 ，从而得到本层的 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b == 0)
    {
        x = 1,y = 0;
        return a;
    }
    ll d = exgcd(b,a % b,y,x);
    y -= (a / b) * x;
    return d;
}
ll qpow(ll a, ll b, ll m) 
{
    ll res = 1;
    a %= m;
    while (b) 
    {
        if (b & 1) 
        {
            res = res * a % m;
        }
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
ll phi(ll n) 
{
    ll res = n;
    for (int i = 2; 1ll * i * i <= n; i++) 
    {
        if (n % i == 0)
            res = res / i * (i - 1);
        while (n % i == 0)
            n /= i;
    }
    if (n > 1)
        res = res / n * (n - 1);
    return res;
}
ll calc(ll a,ll m)
{
    if(m == 1)
    {
        return 1;
    }
    ll p = phi(m);
    ll x,y;
    ll g = exgcd(m,p,x,y);
    ll pre = calc(a,g); 
    ll v = (qpow(a,pre,m) - pre) % m;
    if(v < 0)
        v += m;
    ll res = (v / g) * y % (m / g);
    if(res < 0)
    {
        res += m / g;
    }
    pre += res * p;
    return pre;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        ll a,m;
        cin >> a >> m;
        cout << calc(a,m) << endl;
    }
}