Problem Description

“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

題意：t 組數據，每組給出一個十進制數 n，現可將其轉為任意進制，但要求轉換后的數只由?3、4、5、6 構成的，問滿足條件的進制有幾種，若有無數個，則輸出 -1

思路： 對于任何一種進制 x，均滿足 n=A0+A1*x+A2*x^2+A3*x^3+...，因此可對 n 轉換后的進制位數進行分情況處理

• 對于一位的情況，很明顯有無窮個，即 -1
• 對于兩位的情況，有 n=A0+A1*x 的形式，枚舉 A0、A1，判斷是否有整數解 x，此外，還需判斷 x 是否大于 A0、A1 的最大值
• 對于三位的情況，有 n=A0+A1*x+A2*x^2，枚舉 A0、A1、A2，判斷是否有整數解 x，此外，還需判斷 x 是否大于 A0、A1、A2 的最大值
• 對于四位的情況，由于 n 最大為 1E12，此時最多也只有 7000 個數，而 7000^3 接近 1E12，因此直接枚舉進制數來判斷即可，不必考慮更多的可能

因此，可以枚舉進制然后判斷是否滿足題設

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define PI acos(-1.0) #define E 1e-6 #define MOD 1000000007 #define INF 0x3f3f3f3f #define N 1001 #define LL long long using namespace std; LL max(LL a,LL b,LL c){return max(a,max(b,c)); } int main(){int t;scanf("%d",&t);int Case=1;while(t--){LL n;scanf("%lld",&n);LL res=0;if(n>=3&&n<=6){//一位的情況res=-1;}else{for(LL i=3;i<=6;i++){//兩位的情況for(LL j=3;j<=6;j++){LL k=(n-j)/i;if(k*i==n-j&&k>max(i,j))res++;}}for(LL i=3;i<=6;i++){//位的情況for(LL j=3;j<=6;j++){for(LL k=3;k<=6;k++){LL a=i,b=j,c=k-n;LL delta=b*b-4*a*c;if(delta>0){LL d=sqrt(delta);if(d*d==delta){LL x=(-b+d)/(2*a);if(x>max(i,j,k)&&x*2*a==(-b+d))res++;}}}}}for(LL i=2;i<=7000;i++){//四位的情況LL temp=n,bit;LL num=0;bool flag=true;while(temp){bit=temp%i;temp=temp/i;num++;if(bit<3||bit>6){flag=false;break;}}if(flag&&num>3)res++;}}printf("Case #%d: %lld\n",Case++,res);}return 0; }

?

總結

以上是生活随笔為你收集整理的Lucky Number（HDU-4937）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。