2016.1.26
|
试题描述
|
|
给定n个一次同余方程x mod mi=ai，这里i=0,1,2，……，n-1，给定数据保证所有的mi两两互素。求该方程组的解。 |
|
输入
|
|
第一行包含一个正整数n，接下来的n行，每行包括两个整数，对应一个同余方程，第一个数为mi，第二个数为ai，两数间用一个空格分隔。
|
|
输出
|
|
一个数，表示方程组的解。
|
|
输入示例
|
|
3
3 2 5 3 7 2 |
|
输出示例
|
|
23
|
|
其他说明
|
|
数据范围：所有给定的数据均在int32范围内，且保证所有的数据都符合题目描述的要求，结果在long long范围内。
|
中国剩菜定理嘛ヾ(o?∀?)?
#include<iostream> using namespace std; int m[101],a[101]; void exgcd(int a,int b,int &x,int &y) { if(!b) { x=1; y=0; return; } exgcd(b,a%b,y,x); y=y-a/b*x; } int main() { long long total=1,ans=0; int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&m[i],&a[i]); total*=m[i]; } for(int i=1;i<=n;i++) { int M=total/m[i]; int x,y; exgcd(M,m[i],x,y); ans=(ans+a[i]*M*x)%total; } printf("%d",(ans+total)%total); }
原文：http://www.cnblogs.com/16er/p/5159609.html
