关于gcd和exgcd的一道ICPC题的解法与回顾部分知识点

cjcf / 2024-09-26 / 原文

$gcd$的本质原理

$gcd(x,y)$与$gcd(y,$x%y$)$之所以等价
证明如下：
设$x$与$y$的本质公约数为d
$x=m*d$,$y=n*d$
令$x/y=k$
$x$%y$==x-x/y*y==m*d-k*n*d==(m-n*k)d$
如果$x$是$y$的倍数，则$m-n*k==0$,返回$y$
否则,数值缩小进一步靠近最大公约数
代码

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	else return gcd(b, a % b);
}

$exgcd(x,y,x1,y1)$的原理

$exgcd(x,y,x1,y1)$能求出对于一个方程$ax+by=gcd(x,y)$符合条件的$x$和$y$，其中返回$x1=x$,$y1=y$
当$y==0$时,$x1=1,y=0$是$exgcd(x,y,x1,y1)=gcd(x,y)$的唯一正解
又加上
$gcd(x,y)=gcd(y,x$%$y)$
所以$a0x+b0y=a1y+(x$%$y)b1=a1y+(x-x/y*y)b1=b1*x+(a1-x/y*b1)y$
$a0=b1,bo=a1-x/y*b1$
于是递归得解
代码

void exgcd(ll x, ll y, ll &x1, ll &y1)
{
	if (y == 0)
	{
		x1 = 1;
		y1 = 0;
		return;
	}
exgcd(y, x % y, x1, y1);
	ll t = x1;
	x1 = y1;
	y1 = t - x / y *y1 ;
}

裴蜀定理

对于非负整数$a,b$,存在$x,y$使得$ax+by=gcd(a,b)$,即$ax+by$能构成的最小正整数就是$gcd(a,b)$，$a，b$不可同时为0
多理解即可

题目时间！！！

Modulo Ruins the Legend

题目链接，QOJ：https://qoj.ac/problem/5301
codforces：https://codeforces.com/gym/104090/problem/A

#include<iostream>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#include<bitset>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<time.h>
#include<random>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	else return gcd(b, a % b);
}
ll ksm(ll x, ll y)
{
	ll ans = 1;
	while (y)
	{
		if (y & 1)
			ans *= x;
		x *= x;
		y >>= 1;
	}
	return ans;
}
void fio()
{
	ios::sync_with_stdio();
	cin.tie(0);
	cout.tie(0);
}
ll a[100500];
void exgcd(ll a, ll b, ll &x, ll &y)
{
	if (b == 0)
	{
		x = 1;
		y = 0;
		return;
	}
exgcd(b, a % b, x, y);
	ll t = x;
	x = y;
	y = t - a / b * y;
}
int main()
{
	fio();
	ll n, m;
	cin >> n >> m;
	ll sum = 0;
	for (ll i = 1; i <= n; i++)
	{
		cin >> a[i];
		sum += a[i];
	}
	ll x = gcd(n, n * (n + 1) / 2);
	ll y = gcd(x, m);//裴蜀定理，求最小,随后移项会变成k1*y=-sum+k
	ll k = y - (y - sum % y);//最小的k,直接先求最小值k，最后k等价于sum%y
	ll j = -sum / y;//y其实乘以了j
	cout << k << endl;
	//如何求逆解？
	ll x1, y1;
	exgcd(x, m, x1, y1);
	ll x2, y2;
	x1 = (x1 % m * (j % m)) % m;//最后答案是模m的，先把j乘上，最后再对m取模
	exgcd(n, n * (n + 1) /2 , x2, y2);
	x2 =x2%m*(x1%m)%m;
	y2 =(y2%m* (x1%m))%m;
	cout << (x2 % m + m) % m << " " << (y2 % m + m) % m<<endl;
}