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个数 PM ,中间用空格分隔, P 是质数, MK % 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 排序,然后让 K2+1=3 开始,步长为 2 ,因为这样刚好满足第一个条件,然后找到了 5 满足第二个条件,然后以 23 的最小公倍数为步长继续枚举,直到满足第三个条件,当然条件如果较多也可以使用这种办法。

 

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;
}