Lucky --- DYOI系列题解
MuLinnnnn
·
·
算法·理论
看到题以后也许你已经知道要干什么了。
简略题意：给定 a,p 求 b 使得 a\times b\bmod p=1。
观察可知，如果 a \bmod p =0 或 p \bmod a =0 即 a|p 或 p|a， b 无解。
换句话说，a,p 必须互质，即 \gcd(a,p)=1。
求一组解且 \gcd(a,p)=1 自然想到 扩展欧几里得算法。
总代码：
```
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll read(){
ll x = 0,f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-'){
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar();
}
return x * f;
}
void write(ll x) {
if(x < 0) {
x = -x;
putchar('-');
}
if(x > 9) {
write(x / 10);
}
putchar(x % 10 +'0');
}
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, x, y);
ll tmp = x;
x = y;
y = tmp - (a / b) * y;
return d;
}
int main(){
ll T;
T = read();
while(T--){
ll a, p;
cin >> a >> p;
if(a % p == 0 || p % a == 0){
putchar('N'), putchar('o');
putchar('\n');
// cout << "No" << endl;
continue;
}
if(p == 1){
putchar('1'), putchar('\n');
continue;
}
a = (a % p + p) % p;
if(a == 0){
putchar('N'), putchar('o');
putchar('\n');
continue;
}
ll x, y;
ll d = exgcd(a, p, x, y);
if(d != 1){
putchar('N'), putchar('o');
putchar('\n');
}else{
x = (x % p + p) % p;
write(x);
putchar('\n');
}
}
return 0;
}
```
代码使用快读快写。多测即可通过本题。