Another Easy Problem fzu1753

Another Easy Problem

Time Limit: 1000MS

Memory Limit: 32768KB

64bit IO Format: %I64d & %I64u

[Submit] [Go Back] [Status]

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

Sample Output

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #include<time.h>
 5 #include<iostream>
 6 #include<algorithm>
 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<t; i++)
31     {
32         m=n;
33         sum=0;
34         while(m)
35         {
36             m/=p[i];
37             sum+=m;
38         }
39 
40         m=k;
41         while(m)
42         {
43             m/=p[i];
44             sum-=m;
45         }
46 
47         m=n-k;
48         while(m)
49         {
50             m/=p[i];
51             sum-=m;
52         }
53         if(pp[i]!=-1)
54         pp[i]=pp[i]>sum?sum:pp[i];
55         else pp[i]=sum;
56     }
57 }
58 int pow3(int a,int b)//求a^b
59 {
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<t; i++)
85         {
86             if(pp[i])
87                 sum*=pow3(p[i],pp[i]);
88         }
89         printf("%I64d
",sum);
90     }
91 }

View Code