首页 > 代码库 > HDU 4937 Lucky Number 搜索
HDU 4937 Lucky Number 搜索
题意：
给你一个数，求在多少种不同的进制下这个数每一位都是3、4、5、6中的一个。
思路：
搜索。枚举这个数在任意进制下的表示，判断是否合法。当数字只有3、4、5、6时，必定有无穷种。
因为数字太大，所以直接枚举必定会超时。
下面有两种剪枝的方法：
1. 先枚举最后一位的情况。 假设数字n在base进制下表示为 a[n]...a[0]，即 n = a[0] + a[1]*base^1 + ... + a[n]*base^n。
则 n - a[0] = a[1]*base^1 + ... + a[n]*base^n = base * (a[1] + ... + a[n]*base^(n-1) )。 即n - a[0] 是base 的倍数。
所以，我们可以确定base是n-a[0]的因子。 所以，我们可以先枚举在某个进制下的末位a[0]，然后在枚举 n-a[i]的因子就好了。
代码如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <string> 8 #include <queue> 9 #include <stack> 10 #include <vector> 11 #include <map> 12 #include <set> 13 #include <functional> 14 #include <time.h> 15 16 using namespace std; 17 18 typedef __int64 ll; 19 20 const int INF = 1<<30; 21 const int MAXN = (int) 1e6+5; 22 23 int Prime[MAXN], len; 24 bool is[MAXN]; 25 26 ll f[20]; 27 int cnt[20], num; 28 29 void factor(ll x) { //分解质因数 30 num = 0; 31 if (x==1) return ; 32 for (int i = 0; i < len; i++) if ((x%Prime[i])==0) { 33 f[num] = Prime[i]; 34 cnt[num] = 0; 35 while (x%Prime[i]==0) { 36 x /= Prime[i]; 37 cnt[num]++; 38 } 39 num++; 40 if (x==1) break; 41 if (x<Prime[len-1] && !is[x]) break; 42 } 43 if (x!=1) { 44 f[num] = x; 45 cnt[num++] = 1; 46 } 47 } 48 49 ll n; 50 int ans; 51 52 void dfs(ll base, int deep) { //枚举可以重复的组合 53 if (deep==num) { 54 if (base < 4) return ; 55 ll tmp = n, t; 56 while (tmp) { 57 t = tmp%base; 58 if (!(2<t&&t<7)) return ; 59 tmp /= base; 60 } 61 ans++; 62 return ; 63 } 64 ll tmp = base; 65 for (int i = 0; i <= cnt[deep]; i++) { 66 dfs(tmp, deep+1); 67 tmp *= f[deep]; 68 } 69 } 70 71 void solve() { 72 scanf("%I64d", &n); 73 ans = 0; 74 if (2<n&&n<7) { 75 puts("-1"); 76 return ; 77 } 78 for (int i = 3; i < 7; i++) if (n-i>10) { //枚举末位 79 factor(n-i); 80 dfs(1LL, 0); 81 } 82 printf("%d\n", ans); 83 } 84 85 int main() { 86 #ifdef Phantom01 87 freopen("HDU4937.in", "r", stdin); 88 #endif //Phantom01 89 90 memset(is, false, sizeof(is)); 91 len = 0; 92 for (int i = 2; i < MAXN; i++) if (!is[i]) { 93 Prime[len++] = i; 94 for (ll j = i*2; j < MAXN; j+=i) 95 is[j] = true; 96 } 97 98 int T; 99 scanf("%d", &T);100 for (int i = 1; i <= T; i++) {101 printf("Case #%d: ", i);102 solve();103 }104 105 return 0;106 }
2. 当n在base进制下为一位数的时候，为3、4、5、6，则一定存在无穷种进制下都是这个一位数。
两位数时， n = a[1]*base + a[0]
三位数时，n = a[2]*base^2 + a[1]*base + a[0]
因此，在n是两位数或者三位数时，我们可以枚举这个两位数或者三位数，求得有多少个base能得到这个两位数或三位数。
当 n 是4位数或者更多时， n = a[0] + a[1]*base^1 + ... + a[n]*base^n > 3*base^4 。即 3*base^4 < n <= 1e12。 所以，此时base < 7000。
所以，我们可以暴力枚举n是四位数的情况，而这时的base不会大于7000 。所以就不会超时了。
代码如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <string> 8 #include <queue> 9 #include <stack> 10 #include <vector> 11 #include <map> 12 #include <set> 13 #include <functional> 14 #include <time.h> 15 16 using namespace std; 17 18 typedef __int64 ll; 19 const int INF = 1<<30; 20 21 ll n; 22 int ans; 23 24 inline int function1(ll a, ll b) { //n = a*base + b 25 if (((n-b)%a)!=0) return 0; //如果不是整数 26 ll tmp = (n-b)/a; 27 if (a>=tmp || b>=tmp) return 0; //如果位数大于进制数 28 return 1; 29 } 30 31 inline int function2(ll a, ll b, ll c) { //n = a*base^2 + b*base + c 32 c -= n; 33 ll t1 = b*b-4*a*c; 34 if (t1<0) return 0; 35 ll t2 = (ll) sqrt((double)t1); 36 if (t2*t2!=t1) return 0; 37 if (((t2-b)%(2*a))!=0) return 0; 38 t1 = (t2-b)/2/a; 39 if (t1<=a || t1<=b || t1<=c || t1<=0) return 0; 40 return 1; 41 } 42 43 inline bool check(int base) { 44 ll t = n, cnt = 0, tt; 45 while (t>0) { 46 tt = t%base; 47 if (!(2<tt&&tt<7)) return false; 48 t /= base; 49 cnt++; 50 } 51 return cnt>3; 52 } 53 54 void solve() { 55 scanf("%I64d", &n); 56 57 if (2<n&&n<7) { 58 puts("-1"); 59 return ; 60 } 61 62 ans = 0; 63 for (int i = 3; i < 7; i++) { 64 for (int j = 3; j < 7; j++) { 65 for (int k = 3; k < 7; k++) { 66 ans += function2(i, j, k); 67 } 68 ans += function1(i, j); 69 } 70 } 71 ll len = min(n, 7000ll); 72 for (int i = 4; i < len; i++) 73 ans += check(i) ? 1 : 0; 74 75 printf("%d\n", ans); 76 } 77 78 79 void ttt(int i) { 80 int t = 255; 81 printf("%d:", i); 82 while (t) { 83 printf("%d ", t%i); 84 t /= i; 85 } 86 puts(""); 87 } 88 89 int main() { 90 #ifdef Phantom01 91 freopen("HDU4937.in", "r", stdin); 92 // freopen("HDU4937.txt", "w", stdout); 93 #endif //Phantom01 94 95 int T; 96 scanf("%d", &T); 97 for (int i = 1; i <= T; i++) { 98 printf("Case #%d: ", i); 99 solve();100 }101 102 return 0;103 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。