扩展欧几里德、中国剩余定理
前言
听从大佬的，开始刷数论hhhhhh
- 扩展欧几里得 与 中国剩余定理
http://blog.miskcoo.com/2014/09/chinese-remainder-theorem - 中国剩余定理及其实现
https://blog.csdn.net/u010468553/article/details/38346195 - 中国剩余定理
https://baike.baidu.com/item/%E5%AD%99%E5%AD%90%E5%AE%9A%E7%90%86/2841597?fr=aladdin&fromid=11200132&fromtitle=%E4%B8%AD%E5%9B%BD%E5%89%A9%E4%BD%99%E5%AE%9A%E7%90%86
青蛙的约会 - POJ - 1061
思路
题目求解的是 (x + km)%L = (y + kn)%L 这一方程中的k，这一方程可以化为 x + km - aL = y + kn - bL，进而化为 k(n - m) + (a - b)L = x - y，也就是扩欧的形式 ax + by = c，将其解除，其中x的位置就是k，也就是答案
#include<cstdio>
using namespace std;
typedef long long ll;
ll extgcd(ll a, ll b, ll& x, ll& y){
ll d = a;
if(!b){
x = 1, y = 0;
}else{
d = extgcd(b, a%b, y, x);
y -= (a/b) * x;
}
return d;
}
int main(){
ll p, q, m, n, l;
while(~scanf("%lld%lld%lld%lld%lld", &p, &q, &m, &n, &l)){
ll x, y;
ll a = n - m;
ll b = l;
ll c = p - q;
ll d = extgcd(a, b, x, y);
if(c%d != 0){
puts("Impossible");
}else{
a /= d;
b /= d;
c /= d;
ll ans = (x*c%b + b)%b;
printf("%lld\n", ans);
}
}
}
The Balance - POJ - 2142
题意
求解ax + n = by 与 ax = n + by中 x + y 最小，ax + by 尽量小的解
思路
这题个人也是一知半解 T^T
首先求得解，再令其分别取得x与y的最小整数解，最后比较两组解x + y的大小，输出答案
原因嘛，其中一部分是因为 |x| + |y| = |x0 + b/d * t | + |y0 - a/d * t|，当t=0时取得最小解，所以取x与y的最小整数解得到两解作比较，但是ax + by尽量小似乎？没用到？？
#include<cstdio>
using namespace std;
typedef long long ll;
inline int mabs(int x){ return x < 0 ? -x : x; }
int extgcd(int a, int b, int& x, int& y){
int d = a;
if(!b){
x = 1, y = 0;
}else{
d = extgcd(b, a%b, y, x);
y -= (a/b) * x;
}
return d;
}
int main(){
int a, b, c;
while(~scanf("%d%d%d", &a, &b, &c) && (a + b + c)){
int x1, y1, x2, y2;
int g = extgcd(a, b, x1, y1);
a /= g;
b /= g;
c /= g;
x2 = ((x1*c)%b + b)%b;
y2 = mabs((c - a*x2)/b);
y1 = ((y1*c)%a + a)%a;
x1 = mabs((c - b*y1)/a);
if(x1 + y1 < x2 + y2){
printf("%d %d\n", x1, y1);
}else{
printf("%d %d\n", x2, y2);
}
}
}
Biorhythms - POJ - 1006
题意
给定a, b, c, d, 求解 x = a(mod 23), x = b(mod 28), x = c(mod 33)，的x(x > d)，输出 x - d
思路
中国剩余定理裸题（互质）
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 3;
typedef long long ll;
int m[N] = {23, 28, 33};
int a[N];
int m_tot = 23*28*33;
int extgcd(int a, int b, int& x, int& y){
int d = a;
if(!b){
x = 1, y = 0;
}else{
d = extgcd(b, a%b, y, x);
y -= a/b*x;
}
return d;
}
int res(){
int ans = 0;
for(int i = 0; i < N; i++){
int mt = m_tot/m[i];
int t, y;
extgcd(mt, m[i], t, y);
ans += a[i] * t * mt;
}
return (ans%m_tot + m_tot)%m_tot;
}
int main(){
int t;
scanf("%d", &t);
while(t--){
int d = 0, csn = 0;
while(scanf("%d%d%d%d", &a[0], &a[1], &a[2], &d) && (~a[0] || ~a[1] || ~a[2] || ~d)){
int ans = res();
while(ans <= d) ans += m_tot;
printf("Case %d: the next triple peak occurs in %d days.\n", ++csn, ans - d);
}
}
}
Strange Way to Express Integers - POJ - 2891
题意
给定k组数，每组数满足 x = ri(mod ai)，求最小的x，如无解，输出-1
思路
中国剩余定理裸题（非互质）
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
const int N = 1e3 + 15;
ll a[N], m[N];
ll extgcd(ll a, ll b, ll& x, ll& y){
ll d = a;
if(!b){
x = 1, y = 0;
}else{
d = extgcd(b, a%b, y, x);
y -= a/b*x;
}
return d;
}
ll crt(ll n){
if(n == 1){
return (m[0] > a[0] ? a[0] : -1);
}else{
for(int i = 1; i < n; i++){
if(m[i] <= a[i]) return -1;
ll x, y;
ll d = extgcd(m[0], m[i], x, y);
if((a[i] - a[0])%d != 0) return -1;
ll t = m[i]/d;
ll k = ((a[i] - a[0])/d*x%t + t)%t;
a[0] = m[0] * k + a[0];
m[0] = m[0] * m[i]/d;
a[0] = (a[0]%m[0] + m[0])%m[0];
}
}
return a[0];
}
int main(){
ll n;
while(~scanf("%lld", &n)){
for(int i = 0; i < n; i++){
scanf("%lld%lld", &m[i], &a[i]);
}
printf("%lld\n", crt(n));
}
}
