首页 > 代码库 > HDU 4937 Lucky Number 乱搞 + 优化
HDU 4937 Lucky Number 乱搞 + 优化
题意:给你一个数n (1- 1e12),问你有多少种进制使得 这个数用这个进制表示只有 3 . 4 . 5. 6 这4个数
解题思路:这里本来是想要枚举的,发现数太大了,这里利用到了一中很巧妙的优化方法,将 2位 和3位转化成为 一元一次 和一元二次方程,就可以有很大的优化,然后只需要枚举到7000即可
1 // File Name: 1003.cpp 2 // Author: darkdream 3 // Created Time: 2014年08月12日 星期二 12时01分53秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 LL hs[100]; 28 map<long long ,int> a; 29 LL sum ; 30 LL solve(LL n ) 31 { 32 LL k = min(n,10000*1ll); 33 for(LL i = 4;i <= 7000;i ++) 34 { 35 if(a.find(i) != a.end()) 36 continue; 37 LL t = n ; 38 LL ok = 1; 39 while(t) 40 { 41 if(t % i > 6 || !hs[t%i]) 42 { 43 ok = 0 ; 44 break; 45 } 46 t = t / i ; 47 } 48 if(ok) 49 { 50 sum ++ ; 51 } 52 } 53 return sum ; 54 } 55 LL n ; 56 LL solve3(LL i , LL j , LL k ) 57 { 58 double temp = (-j + sqrt(j*j - 4*i*k) )/(2*i); 59 LL tt = (temp+0.5); 60 if(fabs(temp - tt) < 1e-10 && tt > i && tt > j && tt > k+n) 61 { 62 ///printf("%I64d %I64d %I64d %I64d\n",i,j,k+n,tt); 63 return tt; 64 } 65 return 0 ; 66 } 67 int main(){ 68 LL t ; 69 //freopen("intput","r",stdin); 70 //freopen("output1","w",stdout); 71 72 scanf("%I64d",&t); 73 memset(hs,0,sizeof(hs)); 74 for(LL i = 3;i <= 6;i ++) 75 hs[i] = 1; 76 for(LL ca =1 ;ca <= t;ca ++) 77 { 78 a.clear(); 79 scanf("%I64d",&n); 80 if(n <= 6) 81 { 82 if(hs[n]) 83 printf("Case #%I64d: -1\n",ca); 84 else 85 printf("Case #%I64d: 0\n",ca); 86 continue;; 87 } 88 sum = 0 ; 89 for(LL i = 3;i <= 6;i ++) 90 for(LL j = 3;j <= 6;j ++) 91 { 92 LL t= (n-j)/i; 93 if((n-j) % i == 0 && i < t && j < t &&a.find(t) == a.end()) 94 { 95 a[t] = 1; 96 sum ++ ; 97 } 98 for(LL s = 3 ;s <= 6; s ++) 99 {100 t= solve3(i,j,s-n);101 if(t && a.find(t) == a.end())102 {103 a[t] = 1; 104 sum ++ ; 105 }106 }107 }108 //printf("%I64d\n",sum);109 printf("Case #%I64d: %I64d\n",ca,solve(n));110 }111 return 0;112 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。