好赞orz。
对于求一组线性同余方程
x=a[i](mod m[i])
这里任意两个m[i]和m[j]都互质
那么可以用中国剩余定理来做。
对中国剩余定理的理解：（转自matrix67神犇的blog：http://www.matrix67.com/blog/archives/5100）
这些例子通俗易懂，十分赞。
然后是中国剩余定理的解决：
然后模板我是参照了quartergeek神犇和zky神犇的。（三个版本，，sad）
但是我有点疑问，假设这样做，x可能为负数，（当然可以将它变成正的），这样会不会影响到结果？（虽然在本题这样写可以A，但是不知道是不是数据弱。。）
ll china(ll* m, ll* a) {
ll M=1, d, x, y, ret=0;
for1(i, 1, n) M*=m[i];
for1(i, 1, n) {
ll w=M/m[i];
exgcd(w, m[i], d, x, y);
ret=(ret+w*x*a[i])%M;
}
ret=(ret+M)%M;
return ret;
}
先这样写吧。。
（我觉得这样写似乎会错，放上另一个模板，就是将位置调换了一下）
ll china(ll* m, ll* a) {
ll M=1, d, x, y, ret=0;
for1(i, 1, n) M*=m[i];
for1(i, 1, n) {
ll w=M/m[i];
exgcd(m[i], w, d, x, y);
ret=(ret+w*y*a[i])%M;
}
ret=(ret+M)%M;
return ret;
}
反正如果考到好好思考一下应该可以的。
zky神犇是用y来解决的，y肯定是正的
那么本题就是模板题了。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << (#x) << " = " << (x) << endl
#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }
#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endl
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; } typedef long long ll;
const int N=15;
ll a[N], b[N], n;
void exgcd(ll a, ll b, ll &d, ll &x, ll &y) {
if(!b) { d=a; x=1; y=0; return; }
exgcd(b, a%b, d, y, x); y-=a/b*x;
}
ll china(ll* m, ll* a) {
ll M=1, d, x, y, ret=0;
for1(i, 1, n) M*=m[i];
for1(i, 1, n) {
ll w=M/m[i];
exgcd(w, m[i], d, x, y);
ret=(ret+w*x*a[i])%M;
}
ret=(ret+M)%M;
return ret;
}
int main() {
read(n);
for1(i, 1, n) read(a[i]), read(b[i]);
printf("%lld\n", china(a, b));
return 0;
}
2015.4.19 upd：大家请上wiki。。。。即看下边这张图= =（你们就知道我是不是很傻叉啊。。
描述
自从曹冲搞定了大象以后，曹操就开始捉摸让儿子干些事业，于是派他到中原养猪场养 猪，可是曹冲满不高兴，于是在工作中马马虎虎，有一次曹操想知道母猪的数量，于是曹冲想狠狠耍曹操一把。举个例子，假如有16头母猪，如果建了3个猪圈， 剩下1头猪就没有地方安家了。如果建造了5个猪圈，但是仍然有1头猪没有地方去，然后如果建造了7个猪圈，还有2头没有地方去。你作为曹总的私人秘书理所 当然要将准确的猪数报给曹总，你该怎么办？
格式
输入格式
第一行包含一个整数n (n <= 10) – 建立猪圈的次数，解下来n行，每行两个整数ai, bi( bi <= ai <= 1000), 表示建立了ai个猪圈，有bi头猪没有去处。你可以假定ai,aj互质.
输出格式
输出包含一个正整数，即为曹冲至少养母猪的数目。
样例1
样例输入1
样例输出1
来源
huyichen