问题描述:大于1的正整数n可以分解为:n=x1*x2*…*xm。 例如,当n=12 时,共有8 种不同的分解式: 12=12; 12=6*2; 12=4*3; 12=3*4; 12=3*2*2; 12=2*6; 12=2*3*2; 12=2*2*3。 对于给定的正整数n,计算n共有多少种不同的分解式。输入数据只有一行,有1个正整数n (1≤n≤2000000000)。将计算出的不同的分解式数输出。如输入12输出8

一开始的想法是感觉这个问题跟之前的整数分解问题比较像,然而实际上并没有那么简单,因为这个问题的解相比于之前的来说,是有序的,比方2*2*32*3*2就不一样。这里提供两种方法,暂时没有用到动态规划

简单粗暴之递归

看代码就懂是怎么一回事,即把所有可能的开头都遍历一遍,然后利用递归的思想看以该数开头的剩下的数能组成多少种可能累加起来即可,简单易懂。然而慢得很!

int ifp(int n)
{
  if(n==1)
  {
    return 1;
  }else
  {
    int res=0;
    for(int i=2;i<=n;i++)
    {
      if(n%i==0)
      {
        res+=ifp(n/i);
      }
    }
    return res;
  }
}

results:ifp(2000000000)=1223682048 time:249.606s

快一点点的方法:

能不能快一些呢?这是一个问题。有个简单的解决方法就是将每次计算的结果保存下来。因此每次调用函数的时候不用每个数都调用一遍。

map<int,int>resMap;
int ifp(int n)
{
  if(n==1)
  {
    resMap[1]=1;
    return 1;
  }else
  {
    int res=0;
    for(int i=2;i<=n;i++)
    {
      if(n%i==0)
      {
        int nNext=n/i;
        if(resMap.find(nNext)!=resMap.end())
        {
          res+=resMap[nNext];
        }else
        {
          res+=ifp(nNext);
        }
      }
    }
    resMap[n]=res;
    return res;
  }
}

result:ifp(2000000000)=1223682048time:11.5906s//可以忍!不过还是很慢,最后还是等动态规划学完再重新写吧。