首页 > 代码库 > HDU 4937 Lucky Number 乱搞 + 优化

HDU 4937 Lucky Number 乱搞 + 优化

2024-07-17 10:59:09   221人阅读

题意：给你一个数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 }
View Code

 


联系
我们