首页 > 代码库 > 2014多校第七场1003 || HDU 4937 Lucky Number
2014多校第七场1003 || HDU 4937 Lucky Number
题目链接
题意 ： 给定一个十进制n，让你转化成某个进制的数，让这个数只包含3 4 5 6这些数字，这个进制就成为n的幸运数字，输出有多少幸运数字，例如19，5进制表示是34，所以5是19的一个幸运数。
思路 ： 以下思路有这里提供
先考虑特殊情况，所情况下会有无穷个？只有n=3,4,5,6的时候，因为这几个数在大于n的进制下都是他本身。。注意特殊情况不包括33,343这些（我一开始就死在这里了，wa了三次）。因为33在34进制下就不是33了（类似于10在16进制下就是A了）。
我们知道n=a0+a1*x+a2*x^2+...，其中x为进制。由于n达到1e12，所以我们分情况讨论。
1）a0形式，我们已经在特殊情况中指出，只有无穷个的时候才会符合条件
2）a0+a1*x形式，枚举a0,a1，我们判断(n-a0)是否能被a1整除，以及x是否大于max(a0,a1)即可。
3）a0+a1*x+a2*x^2，我们枚举a0,a1,a2，那么就相当于解一元二次方程。判断是否有整数解，是否整数解x>max(a0,a1,a2)即可。
4）不在上述三种形式内的，那么进制x最大也不会x^3>n，不然就会变成上述三种的形式。我们就可以枚举进制然后判断是否为幸运进制了。由于x^3<=n，所以复杂度只有1e4。
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #define LL __int64 6 7 using namespace std; 8 9 int main()10 {11 int T, casee = 1;12 scanf("%d",&T);13 while(T--)14 {15 LL n;16 LL ans = 0,i,j,k;17 scanf("%I64d",&n);18 printf("Case #%d: ", casee++);19 if(n >= 3 && n <= 6)20 {21 printf("-1\n");22 continue;23 }24 for( i = 3; i <= 6; i++)25 for(j = 3; j <= 6; j++)26 if((n - i) % j == 0 && (n - i) / j > max(i, j))27 ans++;28 LL s ,a,b,c;29 for( i = 3; i <= 6; i++)30 {31 for(j = 3; j <= 6; j++)32 {33 for(k = 3; k <= 6; k++)34 {35 a = i,b = j,c = k - n;36 s = (LL)sqrt(b * b - 4 * a * c + 0.5);37 if(s * s != (b * b - 4 * a * c)) continue;38 if((s - b) % (2 * a)) continue;39 if((s - b) / (2 * a) > max(i, max(j, k)))40 ans++;41 }42 }43 }44 LL t;45 for(i = 4; i * i * i <= n; i++)46 {47 t = n;48 while(t)49 {50 if(t % i < 3 || t % i > 6) break;51 t = t / i;52 }53 if(!t) ans++;54 }55 printf("%I64d\n", ans);56 }57 return 0;58 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。