找回密码
 欢迎注册
查看: 5594|回复: 8

[讨论] 6f(n)g(n)=n

[复制链接]
发表于 2009-6-20 10:26:31 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
转自: 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 的正整数.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-20 12:40:13 | 显示全部楼层
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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-20 15:02:09 | 显示全部楼层
链接里面的方法是错误的.
不过如果改成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.

评分

参与人数 1鲜花 +2 收起 理由
winxos + 2 是不是应该是54d*9^d?

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-20 16:22:21 | 显示全部楼层
可惜了,无解:


  1. #if 1
  2.     #define _Test_HI
  3.     #define integer CHugeInt
  4. #else
  5.     #define _Test_HX
  6.     #define integer CHugeIntX
  7. #endif

  8. void check(const integer& x,int u,int v,int w,int h)
  9. {
  10.     int c2,c3,c7,sum;
  11.     c2=c3=c7=0,sum=0;
  12.     const char *a=x.GetStr(FS_NORMAL);
  13.     int i,len=strlen(a);
  14.     for(i=0;i<len;i++){
  15.         char c=a[i];
  16.         if(c=='0'||c=='5')return;
  17.         if('0'<c&&c<='9')
  18.             sum+=c-'0';
  19.         switch(c){
  20.         case 2:
  21.             c2++;
  22.             break;
  23.         case 3:
  24.             c3++;
  25.             break;
  26.         case 4:
  27.             c2+=2;
  28.             break;
  29.         case 6:
  30.             c2++,c3++;
  31.             break;
  32.         case 7:
  33.             c7++;
  34.             break;
  35.         case 8:
  36.             c2+=3;
  37.             break;
  38.         case 9:
  39.             c3+=2;
  40.             break;
  41.         }
  42.     }
  43.     sum/=9;c3+=2;
  44.     if(sum==h&&c2+1==u&&c3+1==v&&c7==w){
  45.         printf("%s\n",a);
  46.     }
  47. }

  48. int main(int argc, char* argv[])
  49. {
  50.     int u,v,w,a;
  51.     integer x(108);
  52.     integer b(1);
  53.     for(u=1;u<=103;u++)b*=10;
  54.     for(u=2;u<=342;u++){
  55.         integer ux(x);
  56.         for(v=3;v<=215;v++){
  57.             integer vx(ux);
  58.             for(w=0;w<=121;w++){
  59.                 integer wx(vx);
  60.                 for(a=1;a<=103;a++){
  61.                     integer ax(wx);
  62.                     ax+=wx;
  63.                     if(ax>=b)break;
  64.                     check(ax,u,v,w,a);
  65.                 }
  66.                 wx*=7;
  67.                 if(wx>=b)break;
  68.             }
  69.             vx*=3;
  70.             if(vx>=b)break;
  71.         }
  72.         ux*=2;
  73.         if(ux>=b)break;
  74.     }
  75.     return 0;
  76. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-20 22:18:09 | 显示全部楼层
本帖最后由 winxos 于 2009-6-20 22:19 编辑

3# mathe
这个范围的估计很巧妙。
不是是否是54d呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-20 22:24:30 | 显示全部楼层
4# mathe
CHugeInt
是调用的什么库呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-20 22:29:12 | 显示全部楼层
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型提前返回。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-21 07:48:56 | 显示全部楼层
4# mathe
CHugeInt
是调用的什么库呢?
winxos 发表于 2009-6-20 22:24

是gxqcn的HugeCalc
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-21 07:51:36 | 显示全部楼层
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,如果用乘除运算,显然不会快.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 13:07 , Processed in 0.059062 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表