专栏文章

Lucky --- DYOI系列题解

MMuLinnnnn
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miof8uol
此快照首次捕获于
2025/12/02 18:14
3 个月前
此快照最后确认于
2025/12/02 18:14
3 个月前
查看原文
看到题以后也许你已经知道要干什么了。
简略题意：给定 a,pa,p 求 bb 使得 a×b mod p=1a\times b\bmod p=1。
观察可知，如果 a mod p=0a \bmod p =0 或 p mod a=0p \bmod a =0 即 a∣pa|p 或 p∣ap|a， bb 无解。
换句话说，a,pa,p 必须互质，即 gcd⁡(a,p)=1\gcd(a,p)=1。
求一组解且 gcd⁡(a,p)=1\gcd(a,p)=1 自然想到 扩展欧几里得算法。
ax+py=gcd⁡(a,p)ax+py=\gcd(a,p) 发现 如果满足此式则 a×b mod p=1a\times b\bmod p=1 一定成立，则问题转化为求 ax+py=1ax+py=1 时 xx 的最小值。直接套用扩展欧几里得算法求出并缩小范围至 [0,p−1][0, p-1] 即可。
总代码：
CPP
#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;
}
代码使用快读快写。多测即可通过本题。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...