fzu 1753 质因数的应用

 1 #include <iostream>
 2 #include <cmath>
 3 #include <cstdio>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 typedef __int64 LL;
 8 const int maxn=1e5+5;
 9 int prime[10000],num,n[200],m[200];
10 bool flag[maxn];
11 
12 void init()
13 {
14     memset(flag,true,sizeof(flag));
15     int i,j;num=0;
16     for(i=2;i<maxn;i++)
17     {
18         if(flag[i]) prime[num++]=i;
19         for(j=0;j<num&&i*prime[j]<maxn;j++)
20         {
21             flag[i*prime[j]]=false;
22             if(i%prime[j]==0) break;
23         }
24     }
25 }
26 
27 int factor(int a,int b)
28 {
29     int sum=0;
30     while(b)
31     {
32         sum+=b/a;
33         b/=a;
34     }
35     return sum;
36 }
37 
38 int getfactor(int i,int j)
39 {
40     int sum=factor(prime[i],n[j]);
41     sum-=factor(prime[i],m[j]);
42     sum-=factor(prime[i],n[j]-m[j]);
43     return sum;
44 }
45 
46 LL mypow(LL a,LL b)
47 {
48     LL ret=1;
49     while(b)
50     {
51         if(b&1) ret*=a;
52         a*=a;
53         b>>=1;
54     }
55     return ret;
56 }
57 
58 LL solve(int n,int MAX)
59 {
60     LL ans=1;
61     for(int i=0;i<num&&prime[i]<=MAX;i++)
62     {
63         int min=10000,c;
64         for(int j=0;j<n;j++)
65         {
66             c=getfactor(i,j);
67             min=min<c?min:c;
68         }
69         ans*=mypow(prime[i],min);
70     }
71     return ans;
72 }
73 
74 int main()
75 {
76     init();
77     int i,t,MIN;
78     while(~scanf("%d",&t))
79     {
80         MIN=1e9;
81         for(i=0;i<t;i++)
82         {
83             scanf("%d %d",n+i,m+i);
84             MIN=MIN<n[i]?MIN:n[i];
85         }
86         printf("%I64d\n",solve(t,MIN));
87     }
88     return 0;
89 }