51nod 1079 中国剩余定理

描述

一个正整数 K ，给出 K Mod 一些质数的结果，求符合条件的最小的 K 。

例如， K % 2 = 1 , K % 3 = 2 , K % 5 = 3 。符合条件的最小的 K = 23 。

Input

第1行：1个数 N 表示后面输入的质数及模的数量。（2 <= N <= 10)

第2 – N + 1行，每行2个数 P 和 M ，中间用空格分隔， P 是质数， M 是 K % P 的结果。（2 <= P <= 100, 0 <= K < P)

Output

输出符合条件的最小的 K 。数据中所有 K 均小于 10^9 。

Input示例

3
2 1
3 2
5 3

Output示例

23

思路

下面的AC代码看起来比较暴力的啦！

比如 K % 2 = 1, K % 3 = 2, K % 5 = 3

首先给 2 3 5 排序，然后让 K 从 2+1=3 开始，步长为 2 ，因为这样刚好满足第一个条件，然后找到了 5 满足第二个条件，然后以 2 和 3 的最小公倍数为步长继续枚举，直到满足第三个条件，当然条件如果较多也可以使用这种办法。

AC 代码

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include<algorithm>
#include <queue>
using namespace std;

struct po
{
    int num;
    int last;
} a[105];

bool cmp(po a,po b)
{
    return a.num<b.num;
}
int gcd(int a,int b)
{
    if(a<b)swap(a,b);
    if(b==0)return a;
    return gcd(b,a%b);
}
int main()
{
    int N;
    cin>>N;
    int i;
    for(i=0; i<N; i++)
        cin>>a[i].num>>a[i].last;
    sort(a,a+i,cmp);
    int fri=a[0].num+a[0].last;
    for(int j=0; j<i; j++)
    {
        int s=1;
        for(int k=0; k<j; k++)
            s=s/gcd(a[k].num,s)*a[k].num;
        //cout<<s<<endl;
        for(; fri%a[j].num!=a[j].last; fri+=s);
//            cout<<s<<" "<<fri<<endl;
    }
    cout<<fri<<endl;
    return 0;
}