6f(n)g(n)=n

mathe

转自: http://tieba.baidu.com/f?kz=596137795 设f(n)是n的各位数字之和，g(n)是n各位数字之乘积。{例如：f(25)=2+5=7,g(25)=2x5=10}。找出所有能满足条件6 f(n) g(n) = n 的正整数.

winxos

1# mathe 按照给出地址的讨论，认为第三题是题目错了，无解； 真实的题目如下：

搜了一下 找到题目了 Let f(N) denote the sum of the digits of N and g(N) the product of the digits of N. Find all positive integers N such that 6 f(N) g(N) = N^2.

50000000以内我只找到一个48

mathe

链接里面的方法是错误的. 不过如果改成6f(N)g(N)=N^2,那倒是不难. 首先假设N是d位整数,那么$f(N)<=9*d,g(N)<=9^d,N^2>=100^(d-1)$ 得到$64d*9^d>=100^{d-1}$,于是d<=4.

mathe

可惜了,无解:

3. #if 1
4. #define _Test_HI
5. #define integer CHugeInt
6. #else
7. #define _Test_HX
8. #define integer CHugeIntX
9. #endif
11. void check(const integer& x,int u,int v,int w,int h)
12. {
13. int c2,c3,c7,sum;
14. c2=c3=c7=0,sum=0;
15. const char *a=x.GetStr(FS_NORMAL);
16. int i,len=strlen(a);
17. for(i=0;i<len;i++){
18. char c=a[i];
19. if(c=='0'||c=='5')return;
20. if('0'<c&&c<='9')
21. sum+=c-'0';
22. switch(c){
23. case 2:
24. c2++;
25. break;
26. case 3:
27. c3++;
28. break;
29. case 4:
30. c2+=2;
31. break;
32. case 6:
33. c2++,c3++;
34. break;
35. case 7:
36. c7++;
37. break;
38. case 8:
39. c2+=3;
40. break;
41. case 9:
42. c3+=2;
43. break;
44. }
45. }
46. sum/=9;c3+=2;
47. if(sum==h&&c2+1==u&&c3+1==v&&c7==w){
48. printf("%s\n",a);
49. }
50. }
52. int main(int argc, char* argv[])
53. {
54. int u,v,w,a;
55. integer x(108);
56. integer b(1);
57. for(u=1;u<=103;u++)b*=10;
58. for(u=2;u<=342;u++){
59. integer ux(x);
60. for(v=3;v<=215;v++){
61. integer vx(ux);
62. for(w=0;w<=121;w++){
63. integer wx(vx);
64. for(a=1;a<=103;a++){
65. integer ax(wx);
66. ax+=wx;
67. if(ax>=b)break;
68. check(ax,u,v,w,a);
69. }
70. wx*=7;
71. if(wx>=b)break;
72. }
73. vx*=3;
74. if(vx>=b)break;
75. }
76. ux*=2;
77. if(ux>=b)break;
78. }
79. return 0;
80. }

复制代码

winxos

3# mathe 这个范围的估计很巧妙。 不是是否是54d呢？

winxos

4# mathe CHugeInt 是调用的什么库呢？

winxos

mathe的check函数写成那么多的case是速度会快一些么？ 我的是这样写的，

1. void getsum_mul(__int64 n,__int64 ret[2])
2. {
3. ret[0]=0;
4. ret[1]=1;
5. while (n)
6. {
7. ret[0]+=n%10;
8. ret[1]*=n%10;
9. n/=10;
10. }
11. }

复制代码

不过没有加0和5的处理，加上的话可以改成int型提前返回。

mathe

4# mathe CHugeInt 是调用的什么库呢？ winxos 发表于 2009-6-20 22:24

是gxqcn的HugeCalc

mathe

mathe的check函数写成那么多的case是速度会快一些么？ 我的是这样写的，void getsum_mul(__int64 n,__int64 ret[2]) { ret[0]=0; ret[1]=1; while (n) { ret[0]+=n%10; ret[1]*=n%10; n/=10; } ... winxos 发表于 2009-6-20 22:29

开关语句通常会被编译器翻译成跳转表,不过跳转语句速度也不算太快,通常需要好几个时钟周期(主要在于通常跳转预测会失败) 不过在我的代码里面,使用的是超大整数而不是__int64,如果用乘除运算,显然不会快.