Time Limit: 1000MS

Memory Limit: 32768KB

64bit IO Format: %I64d & %I64u

[]   [Go Back]   []  

Description

xtt最近学习了高斯消元法解方程组,现在他的问题来了，如果是以下的方程，那么应该如何解呢?

C(n1,m1)==0 (mod M)

C(n2,m2)==0 (mod M)

C(n3,m3)==0 (mod M)

................

C(nk,mk)==0 (mod M)

xtt希望你告诉他满足条件的最大的M

其中C(i,j)表示组合数,例如C(5,2)=10,C(4,2)=6...

Input

输入数据包括多组，每组数据的第一行是一个正整数T(1<=T<=150)表示接下来描述的T个方程

接下来T行，每行包括2个正整数ni,mi (1<=mi<=ni<=100000)

Output

输出一行答案，表示满足方程组的最大M。

Sample Input

3100 150 160 1

Sample Output

10

1 #include
        
          2 #include
         
           3 #include
          
            4 #include
           
             5 #include
            
              6 #include
             
               7 using namespace std; 8 int p[100000]= { 0},t,pp[10000]; 9 void init()10 {11 long long i,j;12 t=0;13 for(i=2; i<1000; i++)14 {15 if(!p[i])16 {17 p[t++]=i;18 j=i*i;19 while(j<100000)20 {21 p[j]=1;22 j+=i;23 }24 }25 }26 }27 void fun(int n,int k)28 {29 int i,j,m,sum;30 for(i=0; i
              
               sum?sum:pp[i];55 else pp[i]=sum;56 }57 }58 int pow3(int a,int b)//求a^b59 {60 int r = 1,base = a;61 while(b!= 0 )62 {63 if(b&1)64 r*= base;65 base*= base;66 b>>= 1;67 }68 return r;69 }70 71 int main()72 {73 init();74 int tt,m,n,i;75 while(~scanf("%d",&tt))76 {77 memset(pp,-1,sizeof(pp));78 while(tt--)79 {80 scanf("%d%d",&m,&n);81 fun(m,n);82 }83 long long sum=1;84 for(i=0; i