Lucky Number

“Ladies and Gentlemen, It’s show time! ”

“A thief is a creative artist who takes his prey in style… But a detective is nothing more than a critic, who follows our footsteps…”

Love_Kid is crazy about Kaito Kid , he think 3(because 3 is the sum of 1 and 2), 4, 5, 6 are his lucky numbers and all others are not.

Now he finds out a way that he can represent a number through decimal representation in another numeral system to get a number only contain 3, 4, 5, 6.

For example, given a number 19, you can represent it as 34 with base 5, so we can call 5 is a lucky base for number 19.

Now he will give you a long number n(1<=n<=1e12), please help him to find out how many lucky bases for that number.

If there are infinite such base, just print out -1.

Input

There are multiply test cases.

The first line contains an integer T(T<=200), indicates the number of cases.

For every test case, there is a number n indicates the number.

Output

For each test case, output “Case #k: ”first, k is the case number, from 1 to T , then, output a line with one integer, the answer to the query.

Sample Input

2
10
19

Sample Output

Case #1: 0
Case #2: 1

题意：

输入一个十进制数N，把他转换成其他任意进制数，如果转换之后的某进制数中，所有的数字都属于集合（3,4,5,6）（每个数字都可以出现任意次数），那么记录下此时的基数（不用保存，不用输出），结果+1 。输出符合条件的基数的总个数（如果这样的基数有无限个，则输出-1）.例如19在5进制下是34，所以5是幸运进制

思路：

枚举时，考虑进制的基数最大枚举 1e4 。

AC代码：

#include <cstdio>   //AC  g++  15ms
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    int tt=0;
    while(T--){
        long long int value;
        scanf("%lld",&value);
        if(3 <= value && value <= 6){
            printf("Case #%d: -1\n",++tt);
        }
        else{   //下面开始讨论三种 情况
            long long int ans = 0;
            long long int i,j,k;    //因为 基数可能很大
            for(i=3;i<=6;i++){  //value = i* x + j (x是进制基数)
                for(j=3;j<=6;j++){      // 即 基数 x > 任何一位上面的数字
                    if( (value-j)%i==0 && (value-j)/i > max(i,j))
                        ++ans;
                }
            }
            long long int d,x,c;
            for(i=3;i<=6;i++){  //value = i*x^2 + j*x + k;
                for(j=3;j<=6;j++){
                    for(k=3;k<=6;k++){  //!!! 我的天！用公式求根，前提是 0 = i*x^2 + j*x + C 啊啊啊
                        c = k-value;    //!!!就是这个位置
                        d = (long long int)sqrt(j*j-4*i*c+0.5);
                        if(d*d != (j*j-4*i*c) ) //判断代尔塔 要是整数
                            continue;
                        if( (-j+d)%(2*i)!=0)
                            continue;
                        x = (-j+d)/(2*i);   //要确保 x 的值是 正整数（所以去掉-j-d）
                        if(x > max(i,max(j,k)))
                            ++ans;
                    }
                }
            }
            long long int t;
            for(i=2; i*i*i<=value; i++){ //排除 1 （不然，是死循环）
                t  = value;
                while(t != 0){
                    if((t%i < 3) || (t%i > 6) )
                        break;
                    t = t/i;    //若没有break,说明本次处理结果符合标准
                }
                if(t == 0)  //说明除尽才退出的（所以，记录i ）
                    ++ans;
            }
         //   printf("Case #%d: %I64d\n",++tt,ans); //在VJ 上面用g++ 提交，都对
            printf("Case #%d: %lld\n",++tt,ans);
        }
    }
    return 0;
}