论坛 › 编程擂台 › 6f(n)g(n)=n

mathe 发表于 2009-6-20 10:26:31

6f(n)g(n)=n

转自: 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 发表于 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

mathe 发表于 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.

mathe 发表于 2009-6-20 16:22:21

可惜了,无解:

#if 1
    #define _Test_HI
    #define integer CHugeInt
#else
    #define _Test_HX
    #define integer CHugeIntX
#endif

void check(const integer& x,int u,int v,int w,int h)
{
    int c2,c3,c7,sum;
    c2=c3=c7=0,sum=0;
    const char *a=x.GetStr(FS_NORMAL);
    int i,len=strlen(a);
    for(i=0;i<len;i++){
      char c=a;
      if(c=='0'||c=='5')return;
      if('0'<c&&c<='9')
            sum+=c-'0';
      switch(c){
      case 2:
            c2++;
            break;
      case 3:
            c3++;
            break;
      case 4:
            c2+=2;
            break;
      case 6:
            c2++,c3++;
            break;
      case 7:
            c7++;
            break;
      case 8:
            c2+=3;
            break;
      case 9:
            c3+=2;
            break;
      }
    }
    sum/=9;c3+=2;
    if(sum==h&&c2+1==u&&c3+1==v&&c7==w){
      printf("%s\n",a);
    }
}

int main(int argc, char* argv[])
{
    int u,v,w,a;
    integer x(108);
    integer b(1);
    for(u=1;u<=103;u++)b*=10;
    for(u=2;u<=342;u++){
      integer ux(x);
      for(v=3;v<=215;v++){
            integer vx(ux);
            for(w=0;w<=121;w++){
                integer wx(vx);
                for(a=1;a<=103;a++){
                  integer ax(wx);
                  ax+=wx;
                  if(ax>=b)break;
                  check(ax,u,v,w,a);
                }
                wx*=7;
                if(wx>=b)break;
            }
            vx*=3;
            if(vx>=b)break;
      }
      ux*=2;
      if(ux>=b)break;
    }
    return 0;
}

winxos 发表于 2009-6-20 22:18:09

本帖最后由 winxos 于 2009-6-20 22:19 编辑

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

winxos 发表于 2009-6-20 22:24:30

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

winxos 发表于 2009-6-20 22:29:12

mathe的check函数写成那么多的case是速度会快一些么？
我的是这样写的，void getsum_mul(__int64 n,__int64 ret)
{
        ret=0;
        ret=1;
        while (n)
        {
                ret+=n%10;
                ret*=n%10;
                n/=10;
        }
}不过没有加0和5的处理，加上的话可以改成int型提前返回。

mathe 发表于 2009-6-21 07:48:56

4# mathe
CHugeInt
是调用的什么库呢？
winxos 发表于 2009-6-20 22:24 http://bbs.emath.ac.cn/images/common/back.gif
是gxqcn的HugeCalc

mathe 发表于 2009-6-21 07:51:36

mathe的check函数写成那么多的case是速度会快一些么？
我的是这样写的，void getsum_mul(__int64 n,__int64 ret)
{
        ret=0;
        ret=1;
        while (n)
        {
                ret+=n%10;
                ret*=n%10;
                n/=10;
        } ...
winxos 发表于 2009-6-20 22:29 http://bbs.emath.ac.cn/images/common/back.gif
开关语句通常会被编译器翻译成跳转表,不过跳转语句速度也不算太快,通常需要好几个时钟周期(主要在于通常跳转预测会失败)
不过在我的代码里面,使用的是超大整数而不是__int64,如果用乘除运算,显然不会快.

查看完整版本: 6f(n)g(n)=n