【POJ 2891】Strange Way to Express Integers

题目传送门:http://poj.org/problem?id=2891

这个东西,不保证互质,所以中国剩余定理上不了
于是就得合并方程:
把\(\left\{ \begin{array}{l}
x \equiv {a_1}(Mod{\rm{ }}{b_1})\\
x \equiv {a_2}(Mod{\rm{ }}{b_2})
\end{array} \right.\)
替换成\(x \equiv {a_1} + A \cdot {b_1}(Mod{\rm{ }}\frac{{{b_1} \cdot {b_2}}}{{GCD({b_1},{b_2})}})\)
其中A为\(A \cdot {b_1} – B \cdot {b_2} = {a_2} – {a_1}\)的最小非负整数解
至于推导过程嘛,就自己推一推咯,不想写latex了,太费时间

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

inline LL read(){
	char c=getchar(); LL ret=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

LL GCD(LL a,LL b){return b?GCD(b,a%b):a;}

LL EX_GCD(LL a, LL b, LL &x, LL &y){
	if (!b) {x=1;y=0;}
	else {EX_GCD(b,a%b,y,x);y-=a/b*x;}
}

inline LL EX_GCD(LL a, LL b, LL pur){
	LL ret,tmp; EX_GCD(a,b,ret,tmp);
	return ((ret*pur)%b + b) % b;
}

int main(){
	int n; while (~scanf("%d",&n)) {
		LL b1=read(),a1=read(),a2,b2,tag=0,A,tmp,gcd;
		for (int i=1;i<n;i++) {
			b2 = read(); a2 = read(); gcd = GCD(b1,b2);
			if (!tag) {
				if ((a2-a1)%gcd) tag = 1, printf("-1\n");
				else { 
					A = EX_GCD(b1/gcd,b2/gcd,(a2-a1)/gcd);
					a1 = a1 + (A*b1);
					b1 = b1/gcd*b2; a1 %= b1;
				}
			}
		}
		if (!tag) printf("%lld\n",((a1%b1)+b1)%b1);
	}
	return 0;
} 

另外,这个题,貌似会爆long long,不过只要你的代码跟我的差不多,就能过QAQ
不得不说,这个题目真的是出得辣鸡,数据范围都没给全………

【POJ 1006】Biorhythms

题目传送门:http://poj.org/problem?id=1006
中文版题目:http://hzwer.com/3299.html

完全看不懂题,不过既然大家都说是模线性方程组,那就按照那样做咯!
中国剩余定理的话,看看wiki就明白啦:https://en.wikipedia.org/wiki/Chinese_remainder_theorem

#include<iostream>
#include<cstdio>
using namespace std;

const int SGZ = 3;
const int MAXN = 5;
const int SUM = 23*28*33;

int T,arr[]={0,28*33,23*33,23*28},ori[]={0,23,28,33},a[MAXN],d;

void EX_GCD(int a, int b, int &x, int &y){
	if (!b) x=1, y=0;
	else EX_GCD(b,a%b,y,x), y -= a/b*x;
}

inline int rev(int w, int MOD){
	int ret,tmp; EX_GCD(w,MOD,ret,tmp);
	return ret;
}

int main(){
	while (cin>>a[1]>>a[2]>>a[3]>>d && a[1] != -1) {
		int vout = 0; 
		for (int i=1;i<=SGZ;i++) vout += a[i]*rev(arr[i],ori[i])*arr[i];
		vout = ((vout-d)%SUM+SUM)%SUM; vout = vout?vout:SUM;
		printf("Case %d: the next triple peak occurs in %d days.\n",++T,vout);
	}
	return 0;
}