首页 > 代码库 > hdu 3641 Treasure Hunting 强大的二分
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。