HDU 4937Lucky Number

女爷i 2022-06-10 13:38 134阅读 0赞

# 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;
    }

学习代码：http://blog.csdn.net/a601025382s/article/details/38517783