\(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+kll k = y - (y - sum % y);//最小的k,直接先求最小值k，最后k等价于sum%yll j = -sum / y;//y其实乘以了jcout << 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;
}
