您现在的位置是:首页 > 正文

整数因子分解问题

2024-02-01 02:22:08阅读 4

Problem Description 


大于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共有多少种不同的分解式。 


Input 

1个正整数n (1≤n≤2000000000)。  


Output 

1个正整数,即计算出的不同的分解式数  


Sample Input 

12 


Sample Output 

8


===================================================================================

法(1):简单递归方式求解

<span style="font-size:18px;">#include <cstdio>
#include <iostream>

using namespace std;

int count;

void solve(int n){
    if(n == 1){ //叶子结点
        count ++;
    }else{
        for(int i=2;i<=n;i++){//某一个非叶子结点下的下一层所有子结点
            if(n%i == 0) solve(n/i);
        }
    }
}

int main(){
    int n;
    while(cin >> n){
        count = 0;
        solve(n);
        cout<<"The number of solution is "<<count<<endl;
    }
}</span>

法(2):dp方式求解

#include <iostream>
#include <algorithm>
#include <cstdio>

#define maxn 100
using namespace std;

int yueShu[maxn],length=0;
int dp[maxn]; //dp[i]中保存的是i的解决方案数
void approximateNumber(int n)
{
     int i;
     for(i=1;i*i<n;i++) //
         if(n%i==0)
         {
             yueShu[length ++] = i;
             yueShu[length ++] = n/i;
         }

     if(i*i==n)
         yueShu[length++]=i;

     sort(yueShu,yueShu+length);
}

void dpSolve(int n)
{
     int i;

     dp[0]=1;//yueShu[0]=1,值最小,就只有一个约数。 -|
                                                //   | ->遍历yueShu[maxn]
     for(i=1;i<length;i++)//                        -|
     {
         dp[i]=0;
         for(int j=0;j<i;j++)
             if(yueShu[i]%yueShu[j]==0)
                 dp[i]+=dp[j];
     }
}

/*!
eg:
约数      : 1  2  3  4  6  12
解决方案数: 1  1  1  2  3  8

8= 1 + 1 + 1 + 2 + 3;
12 = 1*12
   = 2*6
   = 3*4
   = [4*3] = (1*4)*3 = (2*2)*3
   = [6*2] = (1*6)*2 = (2*3)*2 = (3*2)*2

12 = 4*3;
而4=(1*4);
  4=(2*2);
故  12 = (1*4)*3;
       = (2*2)*3
所以会加上dp[4]=2
*/
int main()
{
     int n;
     while(cin>>n){
        approximateNumber(n);//求n的约数
        dpSolve(n);

        cout<<dp[length-1]<<endl;
     }

     return 0;
}


网站文章

  • 操作系统国产化现状

    操作系统国产化现状

    在开源操作系统生态不断成熟的背景下,中国的国产操作系统依托开源生态和政策东风正快速崛起,市场潜力巨大,未来发展前景值得期待。中国桌面操作系统当前呈现两大特征:一是Windows+Inte...

    2024-02-01 02:22:01
  • java两个list的数据快速对比 map的使用

    1.思路: 把2个list数据放到map里面,利用map的containsKey进行快速比对 2. //数据1 List list1 = new ArrayList(); //数据2 List list2 = new ArrayList(); Map m...

    2024-02-01 02:21:32
  • PAT乙级-B1032 挖掘机技术哪家强(20)

    为了用事实说明挖掘机技术到底哪家强,PAT 组织了一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。

    2024-02-01 02:21:26
  • Android中的内存管理

    当进程内存不够的时候,安卓会再分配一些内存给各个进程。回收的时候就可能杀死那些正在占用内存的进程。所以操作系统需要有一个合理的杀死占用内存的进程的机制,以保证把副作用降到最低。安卓系统会为每个进程合理...

    2024-02-01 02:21:19
  • Linux驱动中断和定时器

    Linux驱动中断和定时器

    Linux驱动中断和定时器一文搞定中断顶半部,底半部机制,硬件中断,软中断,Tasklet,工作队列,jiffies,定时器

    2024-02-01 02:20:50
  • 【学习笔记】初识websocket及其握手过程

    【学习笔记】初识websocket及其握手过程

    客户端收到应答后,要校验Sec-WebSocket-Key的值,如果该值和计算结果不符,或者不符合上面过程任一要求,则拒绝创建websocket连接。如果客户端校验无误,websocket就握手完成了。

    2024-02-01 02:20:44
  • 栈和队列的区别

    栈和队列的区别 1.规则不同 队列:先进先出 栈:先进后出 2.对插入和删除的限定不同 队列:只能在表的一段进行插入,并在另一端进行删除 栈:只能在表的一端插入和删除 3.遍历数据速度不同 队列:基于...

    2024-02-01 02:20:35
  • java lesson13Homework

    /** * 1. 字符串解析,现有字符串,“卡巴斯基#杀毒软件#免费版#俄罗斯#”,解析出每个元素。 */ package String13Practice; public class String01 { public static void main(String[] args){ String str=&quot;卡巴斯基#杀毒软件#免费版#俄罗斯#&quot;...

    2024-02-01 02:20:28
  • IIS文件上传时间、大小限制,默认4M

    IIS文件上传时间、大小限制,默认4M

    打开IIS,点击网站并定位至所部署的网站,在右边找到《管理——配置编译器》,双击打开修改一下两处第一处第二处转载于:https://www.cnblogs.com/mnxxz/p/11601644.html...

    2024-02-01 02:20:02
  • 杰理之频偏自动校正【篇】

    使能该功能,频偏测试过程中会进行自动校正(需同时开启频偏测试使能)

    2024-02-01 02:19:54