首页 > 代码库 > hdu 4937 Lucky Number ( 进制转换+枚举 )
hdu 4937 Lucky Number ( 进制转换+枚举 )
题意:
有一个数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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。