首页 > 代码库 > hdu 4937 Lucky Number
hdu 4937 Lucky Number
虽然算法清晰的不能再清晰，但是实现总是边角料错这错那。
题目大意：
给出n，找出一些进制，使得n在该进制下仅为3,4,5,6表示
解题思路：
首先，4-10000进制直接枚举计算出每一位
此外，最多只有3位，因为10000进制以上且小于1e12，最多3位，直接枚举每一位计算进制N即可
注意：如果类似我用二分或者直接求二次根式，要开个map储存已经计算出来的N进行判重，虽然数据比较弱可以不用判。最多4^3个吧，多了可能会重。
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <vector>#include <utility>#include <stack>#include <queue>#include <map>#include <deque>#include <cmath>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))using namespace std;long long x,N;int ans;int a[6];map<int,bool> mapp;bool check(long long x){ if(x<N) { if(x>=3 && x<=6) return 1; else return 0; } for(int i=3; i<=min(6,N-1); i++) if((x-i)%N==0 && check((x-i)/N)) return 1; return 0;}void dfs(int p){ if(p==3 || p==4) { long long l=1e4,r=1e12; if(p==4) r=1e6; while(l<r-1) { long long m=(l+r)/2; long long tmp=0; for(int i=1; i<=p-1; i++) tmp=tmp*m+a[i]; if(tmp>x) r=m; else l=m; } long long tmp=0; for(int i=1; i<=p-1; i++) tmp=tmp*l+a[i]; if(tmp==x && l!=1e4 && !mapp[l]) { ans++; mapp[l]=1; } if(l!=r && r!=1e4) { tmp=0; for(int i=1; i<=p-1; i++) tmp=tmp*r+a[i]; if(tmp==x && !mapp[r]) { ans++; mapp[r]=1; } } } if(p==4) return; for(int i=3; i<=6; i++) { a[p]=i; dfs(p+1); }}int main(){ //freopen("1003.in","r",stdin); int tt; scanf("%d",&tt); for(int t=1; t<=tt; t++) { mapp.clear(); scanf("%I64d",&x); printf("Case #%d: ",t); if(x>=3&&x<=6) { printf("-1\n"); continue; } ans=0; for(N=4; N<=10000; N++) if(check(x)) ans++; dfs(1); printf("%d\n",ans); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。