HDU 4937 Lucky Number 乱搞 + 优化

  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 }