lightoj 1319

1319 - Monkey Tradition

PDF (English)

Statistics

Forum

Time Limit: 2 second(s)

Memory Limit: 32 MB

In 'MonkeyLand', there is a traditional game called "Bamboo Climbing". The rules of the game are as follows:

1) There are N monkeys who play this game and there are N bamboos of equal heights. Let the height be L meters.

2) Each monkey stands in front of a bamboo and every monkey is assigned a different bamboo.

3) When the whistle is blown, the monkeys start climbing the bamboos and they are not allowed to jump to a different bamboo throughout the game.

4) Since they are monkeys, they usually climb by jumping. And in each jump, the i^th monkey can jump exactly p_i meters (p_i is a prime). After a while when a monkey finds that he cannot jump because one more jump may get him out of the bamboo, he reports the remaining length r_i that he is not able to cover.

5) And before the game, each monkey is assigned a distinct p_i.

6) The monkey, who has the lowest r_i, wins.

Now, the organizers have found all the information of the game last year, but unluckily they haven't found the height of the bamboo. To be more exact, they knowN, all p_i and corresponding r_i, but not L. So, you came forward and found the task challenging and so, you want to find L, from the given information.

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 12). Each of the next n lines contains two integers p_i (1 < p_i < 40, p_i is a prime) and r_i(0 < r_i < p_i). All p_i will be distinct.

Output

For each case, print the case number and the minimum possible value of L that satisfies the above conditions. If there is no solution, print 'Impossible'.

Sample Input

Output for Sample Input

5 4

7 6

11 3

2 1

3 2

5 3

7 1

Case 1: 69

Case 2: 113

PROBLEM SETTER: TANVIR HASSAN

SPECIAL THANKS: JANE ALAM JAN

贴码先，定理稍后学；

//分析：首先我们先学习下中国剩余定理：中国剩余定理
//在模数mi两两互素的情况下，可以用中国剩余定理求n使其满足：
//n=b1(mod m1)
//n=b2(mod m2)
//n=b3(mod m3)
//....
//我感觉这分析好像没什么卵...
#include <cstdio>
#define LL long long
LL p[45], r[45];
void Exgcd(LL a, LL b, LL &xx, LL &yy)
{
    if(b==0)
    {
        xx=1; yy=0;
        return;    
    }    
    Exgcd(b, a%b, xx, yy);
    LL t=xx; xx=yy; yy=t-a/b*yy;
    return;
} 
LL China(LL s[], LL b[], int k)// s: 模数； b: 余数 
{
    LL n=1, xx, yy;
    LL ans=0;
    for(int i=0; i<k; i++)
        n*=s[i];
    for(int i=0; i<k; i++)
    {
        LL t=n/s[i];
        Exgcd(t, s[i], xx, yy);
        ans=(ans+xx*t*b[i])%n;
    }
    return (ans%n+n)%n;
}
int main()
{
    int t, n, Q=1;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(int i=0; i<n; i++)
            scanf("%lld%lld", &p[i], &r[i]);
        LL ans=China(p, r, n);
        printf("Case %d: %lld
", Q++, ans); 
    } 
    return 0;
}

Poj2891 http://poj.org/problem?id=2891

除数非两两互斥

#include <cstdio>
#include <cmath>
#define LL long long 
const int M = 1e5 + 5; int n;
void Exgcd(LL a, LL b, LL &d, LL &x, LL &y)
{
    if(!b){ d=a; x=1; y=0;}
    else
    {
        Exgcd(b, a%b, d, y, x);
        y -= x*(a/b);
    }
}
LL China(LL m[], LL r[], int n)
{
    LL M=m[1],  R=r[1], x, y, d;
    for(int i=2; i<=n; i++)
    {
        Exgcd(M, m[i], d, x, y);
        if((r[i]-R) % d) return -1;
        x=(r[i] - R) / d * x % (m[i] / d);
        R += x * M;
        M = M / d * m[i];
        R %= M; 
    }
    return R > 0? R : R + M;
}
int main()
{
    while(scanf("%d", &n) != EOF)
    {
        LL a[M], r[M];
        for(int i=1; i<=n; i++)
            scanf("%lld%lld", &a[i], &r[i]);
        printf("%lld
", China(a, r, n));
    }
    return 0;    
}

 1 转载：
 2 
 3 /**********************一般模线性方程组***********************/
 4 
 5 同样是求这个东西。。
 6 X mod m1=r1
 7 X mod m2=r2
 8 ...
 9 ...
10 ...
11 X mod mn=rn
12 
13 首先，我们看两个式子的情况
14 X mod m1=r1……………………………………………………………(1)
15 X mod m2=r2……………………………………………………………(2)
16 则有 
17 X=m1*k1+r1………………………………………………………………(*)
18 X=m2*k2+r2
19 那么 m1*k1+r1=m2*k2+r2
20 整理，得
21 m1*k1-m2*k2=r2-r1
22 令(a,b,x,y,m)=(m1,m2,k1,k2,r2-r1)，原式变成
23 ax+by=m
24 熟悉吧？
25 
26 此时，因为GCD(a,b)=1不一定成立，GCD(a,b) | m 也就不一定成立。所以应该先判 若 GCD(a,b) | m 不成立，则！！！方程无解！！！。
27 否则，继续往下。
28 
29 解出(x,y)，将k1=x反代回（*），得到X。
30 于是X就是这两个方程的一个特解，通解就是 X'=X+k*LCM(m1,m2)
31 这个式子再一变形，得 X' mod LCM(m1,m2)=X
32 这个方程一出来，说明我们实现了(1)(2)两个方程的合并。
33 令 M=LCM(m1,m2)，R=r2-r1
34 就可将合并后的方程记为 X mod M = R。
35 
36 然后，扩展到n个方程。
37 用合并后的方程再来和其他的方程按这样的方式进行合并，最后就能只剩下一个方程 X mod M=R，其中 M=LCM(m1,m2,...,mn)。
38 那么，X便是原模线性方程组的一个特解，通解为 X'=X+k*M。
39 
40 如果，要得到X的最小正整数解，就还是原来那个方法：
41 
42 X%=M;
43 if (X<0) X+=M;
44 
45 这么一来～～大功告成～～

...