题目1 : 数论六·模线性方程组
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Ho：今天我听到一个挺有意思的故事！
小Hi：什么故事啊？
小Ho：说秦末，刘邦的将军韩信带领1500名士兵经历了一场战斗，战死四百余人。韩信为了清点人数让士兵站成三人一排，多出来两人；站成五人一排，多出来四人；站成七人一排，多出来六人。韩信立刻就知道了剩余人数为1049人。
小Hi：韩信点兵嘛，这个故事很有名的。
小Ho：我觉得这里面一定有什么巧妙的计算方法！不然韩信不可能这么快计算出来。
小Hi：那我们不妨将这个故事的数学模型提取出来看看？
小Ho：好！
<小Ho稍微思考了一下>
小Ho：韩信是为了计算的是士兵的人数，那么我们设这个人数为x。三人成排，五人成排，七人成排，即x mod 3, x mod 5, x mod 7。也就是说我们可以列出一组方程：
x mod 3 = 2
x mod 5 = 4
x mod 7 = 6
韩信就是根据这个方程组，解出了x的值。
小Hi：嗯，就是这样！我们将这个方程组推广到一般形式：给定了n组除数m[i]和余数r[i]，通过这n组(m[i],r[i])求解一个x，使得x mod m[i] = r[i]。
小Ho：我怎么感觉这个方程组有固定的解法？
小Hi：这个方程组被称为模线性方程组。它确实有固定的解决方法。不过在我告诉你解法之前，你不如先自己想想怎么求解如何？
小Ho：好啊，让我先试试啊！
输入
第1行：1个正整数, N，2≤N≤1,000。
第2..N+1行：2个正整数, 第i+1行表示第i组m,r，2≤m≤20,000,000，0≤r<m。
计算过程中尽量使用64位整型。
输出
第1行：1个整数，表示满足要求的最小X，若无解输出-1。答案范围在64位整型内。
- 样例输入
-
3
3 2
5 3
7 2 - 样例输出
-
23
裸的中国剩余定理，数据比较强，原来写的过不了，估计相乘爆了64；#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define mod 1000000007
#define inf 999999999
//#pragma comment(linker, "/STACK:102400000,102400000")
int scan()
{
int res = , ch ;
while( !( ( ch = getchar() ) >= '' && ch <= '' ) )
{
if( ch == EOF ) return << ;
}
res = ch - '' ;
while( ( ch = getchar() ) >= '' && ch <= '' )
res = res * + ( ch - '' ) ;
return res ;
}
ll a[];
ll b[];
ll gcd(ll x,ll y)
{
if(y==)
return x;
else
return gcd(y,x%y);
}
void exgcd(ll a, ll b, ll &x, ll &y)
{
if(b == )
{
x = ;
y = ;
return;
}
exgcd(b, a % b, x, y);
ll tmp = x;
x = y;
y = tmp - (a / b) * y;
}
int main()
{
ll x,y,z,i,t;
while(scanf("%lld",&z)!=EOF)
{
for(i=;i<z;i++)
scanf("%lld%lld",&b[i],&a[i]);
ll a1=a[],b1=b[];
ll jie=;
for(i=;i<z;i++)
{
ll a2=a[i],b2=b[i];
ll xx,yy;
ll gys=gcd(b1,b2);
if((a2-a1)%gys)
{
jie=;
break;
}
exgcd(b1/gys,b2/gys,xx,yy);
xx = ((a2-a1)/gys*xx)%(b[i]/gys);//这句是关键
a1= a1+xx*b1;
b1 = b1/gys*b[i];
a1 =((a1%b1)+b1)%b1;
}
if(!jie)
printf("-1\n");
else
printf("%lld\n",a1);
}
return ;
}