首页 > 代码库 > hdu 4937 Lucky Number ( 进制转换+枚举 )

hdu 4937 Lucky Number ( 进制转换+枚举 )

2024-07-17 11:19:55   221人阅读

题意:

有一个数n，问有多少个进制x（基数）使得n转换为x进制后的数字中只有3、4、5、6四个数。


算法：

对于只有一位数的情况，显然3、4、5、6都应该输出-1.
  如果有2位数，假设这2位中高位为a，低位为b，进制为base，则 n = a * base + b，解一元一次方程即可。
  如果有3位数，假设这3为从高到低分别为a、b、c，进制为base，则 n = a * base * base + b * base + c，即一元二次方程即可。
  如果位数>= 4，可以暴力枚举进制数。base>min(3,4,5,6),所以从base=4开始枚举。又因为 x1 + x2 * base + x3 * base * base + x4 * base *base *base + ……>= 3*7000+3 *7000 ^2 +3 * 7000 ^3 = 1.029e12 > max(n).
所以枚举4到7000就可以了。

以上来自于http://blog.csdn.net/lyhvoyage/article/details/38532471

其实大多数是官方题解上的，多了最后那个为什么只要枚举到7000就可以了。。因为x^3以内的已经足以表示n的最大值了。


P.S

菜鸟的神思维记录开始---->

比赛的时候是想到了 进制转换就是把 n表示成  a0 + a1*x+a2*(x^2) + a3*(x^3)+....的形式。

但是碍于时限是1s而且n的范围有1e^12，心想O(n)的复杂度都过不了啊。。。而且也想不通难道还有O(logn)的算法?

这种情况下一般是找规律神马的吧。。。不是有循环节就是有什么特殊的规律吧。。。暴力打表看看吧。。。。

于是在偏离比较正确的思路的道路上越走越远!


其实3-6的循环即使是3个for也完全没什么复杂度啊- -也就4^3而已。。。

为什么算法一定要和n有关呢。。。真是死脑筋。。。。笨得要死啊。。。。

最近好几次都是因为估算复杂度有误导致不敢想和写啊。。


#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

typedef long long ll;

ll max(ll x,ll y)
{
    return x>y?x:y;
}

int main()
{
    int T,cas=1;
    ll n,ans;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%I64d",&n);
        printf("Case #%d: ",cas++);
        ans = 0;
        if(n>=3 && n<=6)
        {
            printf("-1\n");
            continue;
        }
        for(ll i=3;i<=6;i++)
        {
            for(ll j=3;j<=6;j++)
            {
                if((n-i)%j==0 && (n-i)/j>max(i,j))  //进制数必须要大于转化后每一位出现的数
                    ans++;
            }
        }
        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,delta;
                    delta = (ll)sqrt(b*b-4*a*c+0.5);
                    if(delta*delta!=(b*b-4*a*c)) continue; //如果b*b-4*a*c不是完全平方数
                    if((delta-b)%(2*a)) continue;  //如果解不是整数
                    ll tmp = (delta-b)/(2*a);
                    if(tmp>max(i,max(j,k)))
                        ans++;
                }
            }
        }
        for(ll i=4;i*i*i<n;i++)
        {
            ll tmp = n;
            while(tmp)
            {
                ll x = tmp%i;
                if(x<3 || x>6) break;
                tmp/=i;
            }
            if(!tmp) ans++;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}



联系
我们