hdu 3641 Treasure Hunting 强大的二分

 1 /**
 2 大意：给定一组ai,bi .    m = a1^b1 *a2^b2 * a3^ b3 * a4^b4*...*ai^bi 
 3 求最小的x!%m =0
 4 思路: 将ai 质因子分解，若是x!%m=0 那么x！ 质因子分解之后 质因子的个数一定大于等于m的个数。二分求解可得
 5 注意： 二分时，需要将，上下限 设定好，low =0； high = 1ll<<60;
 6 **/
 7 
 8 #include <iostream>
 9 #include <cstring>
10 #include <cmath>
11 using namespace std;
12 
13 long long pri[150];
14 
15 void getApri(long long a,long long b){
16     int cnt;
17     for(int i=2;i*i<=a;i++)if(a%i==0){
18         cnt =0;
19         while(a%i==0){
20             cnt++;
21             a =a/i;
22         }
23         pri[i] += cnt*b;
24         if(a==1)
25             break;
26     }
27     if(a>1)
28         pri[a] += b;
29 }
30 
31 long long cal(long long i,long long x){   x!中有多少个i因子
32     long long ret =0;
33     while(x){
34         x = x/i;
35         ret += x;
36     }
37     return ret;
38 }
39 
40 bool judge(long long x){
41     for(int i=1;i<=100;i++)if(pri[i]){
42         long long tmp = cal(i,x);
43         if(tmp<pri[i])
44             return false;
45     }
46     return true;
47 }
48 
49 int main(){
50     int t;
51     cin>>t;
52     while(t--){
53         memset(pri,0,sizeof(pri));
54         int n;
55         cin>>n;
56         long long a,b;
57         while(n--){
58             cin>>a>>b;
59             getApri(a,b);
60         }
61         long long low = 0,high = 1ll<<60;
62         long long ans;
63         while(low<=high){
64             long long mid  = (low+high)/2;
65             if(judge(mid)){
66                 ans = mid;
67                 high  = mid-1;
68             }
69             else
70                 low = mid +1;
71         }
72         cout<<ans<<endl;
73     }
74 
75     return 0;
76 }