2021牛客寒假算法基础集训营3 A. 模数的世界

发表于 分类于

链接

https://ac.nowcoder.com/acm/contest/9983/A

题意

已知 $a,b$，$x \equiv a \pmod p$，$y \equiv b \pmod p$，求 $gcd(x,y) \bmod p$ 的最大值以及 $x,y$ 的取值。

思路

当 $a,b$ 不都为 $0$ 时，最大值必为 $p-1$。

$\begin{cases}
(p-1)k_1%p=a \
(p-1)k_2%p=b
\end{cases}$ 可推出可行解： $\begin{cases}
k_1=t_1p-a \
k_2=t_2p-b
\end{cases}(t1,t2 \ge 1)$

要保证 $k_1,k_2$ 互质，令 $k_2=p-b$，$(t_1p-a)%k_2=1 \Longrightarrow t_1p+mk_2=1+a$。

因为 $k_2,p$ 互质，所以此方程必有解。

代码

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
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
//head
LL exgcd(LL a,LL b,LL &x,LL &y) {
    if(!b) {x=1,y=0;return a;}
    LL ret=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return ret;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--) {
        LL a,b,p;
        cin>>a>>b>>p;
        LL k1=p-a,k2=p-b,x,y;
        if(!a&&!b) cout<<0<<' '<<0<<' '<<0<<'\n';
        else {
            exgcd(p,k2,x,y);
            x=(x%k2+k2)%k2;
            if(!x) x+=k2;
            x*=1+a;
            k1=x*p-a;
            cout<<p-1<<' '<<k1*(p-1)<<' '<<k2*(p-1)<<'\n';
        }
    }
    return 0;
}