hdoj 4937 Lucky Number【想法】

灰太狼 2022-08-10 13:46 20阅读 0赞

题目：[hdoj 4937 Lucky Number][]

来源：[2014 Multi-University Training Contest 7][]

分类：想法题

题意；给出一个数n，然后把这个数用任意进制表示使得其各个位只由3,4,5,6组成，求满足这个条件的进制最多由多少个？

分析：最近比赛状态非常不好，编程经常犯小错误，无法深入思考一个题目，其实这个题目很简单。

我们容易想到暴力的方法，从二进制表示到n进制表示，然后判断满足条件计数，但是n很大，显然超时。

但是，我们可以换一种思路，把n表示成为 k 位 （位数）的数来暴力，一个数的最多位数是2^k==n，题目中n为10^12次方，这样的负责度是允许的，但是编程不好实现。

那么我们可以不可结合一下，对于二位和三位的我们求表示满足条件，其他的枚举 n 进制，显然2位和3为求出来之后，n的循环次数变为k\*k\*k==n，这样大概10^4，显然可以通过，这个题目需要深入分析然后尝试优化，代码很简单：

#include <cstdio>
    #include <cstring>
    #include <string>
    #include <queue>
    #include <stack>
    #include <map>
    #include <vector>
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <set>
    #include <utility>
    #define Del(a,b) memset(a,b,sizeof(a))
    using namespace std;
    long long solve_bit(long long x)
    {
        long long ans=0;
        while(x)
        {
            x/=10;
            ans++;
        }
        return ans;
    }
    int main()
    {
        long long T;
        scanf("%I64d",&T);
        for(long long cas=1; cas<=T; cas++)
        {
            long long n;
            scanf("%I64d",&n);
            long long bit=solve_bit(n);
            long long ans=0;
            if(bit==1)
            {
                if(n==3 || n==4 || n==5 || n==6)
                    ans=-1;
            }
            else
            {
                for(long long i=3; i<=6; i++)
                {
                    for(long long j=3; j<=6; j++)
                        if((n-j)%i==0)
                        {
                            long long t=(n-j)/i;
                            if(t>j && t>i)
                            {
                                //printf("%I64d %I64d %I64d\n",i,t,j);
                                ans++;
                            }
                        }
                }
                for(long long i=3; i<=6; i++)
                {
                    for(long long j=3; j<=6; j++)
                    {
                        for(long long k=3; k<=6; k++)
                        {
                            long long a=i;
                            long long b=j;
                            long long c=k-n;
                            long long d=(long long)sqrt(b*b-a*c*4+0.5);
                            if(d*d!=b*b-a*c*4)continue;
                            if((d-b)%(a*2))continue;
                            long long x=(d-b)/(a*2);
                            if(x>max(max(i,j),k))
                            {
                                ans++;
                            }
                        }
                    }
                }
              for(long long bes=2;bes*bes*bes<=n;bes++)
                {
    
                    long long t=n;
                    while(t)
                    {
                        if(t%bes<3||t%bes>6) break;
                        t/=bes;
                    }
                    if(!t) {ans++;}//printf("%d\n",bes);}
                }
            }
            printf("Case #%I64d: %I64d\n",cas,ans);
        }
    }

[hdoj 4937 Lucky Number]: http://acm.hdu.edu.cn/showproblem.php?pid=4937
[2014 Multi-University Training Contest 7]: http://acm.hdu.edu.cn/search.php?field=problem&key=2014%20Multi-University%20Training%20Contest%207&source=1&searchmode=source