整數因子分解代码,C代码库,德仔网

代码语言

代码分类

【C】整數因子分解

作者:電泡泡 / 发布于2013/5/6/ 602

遞歸用時不划算動態規劃解決


	#include <iostream>
	#include <algorithm>
	#include <stdio.h>
	using namespace std;

	int a[10000], dp[10000], k=0, n;

	void
	ul(int n)
	{
	 int i;
	 for(i=1; i*i<n; i++){
	
	 if(0==n%i){
	 a[k++]=i;
	 a[k++]=n/i;
	 }
	 }
	 if(i*i==n)
	 a[k++]=i;
	}

	void
	solve(int n)
	{
	 int i, j;
	 dp[0]=1;
	 for(i=1; i<k; i++){
	 dp[i]=0;
	 for(j=0; j<i; j++)
	 if(a[i]%a[j]==0)
	 dp[i]+=dp[j];
	 }
	}

	int
	main()
	{
	 cin>>n;
	 ul(n);
	 sort(a, a+k);
	 solve(n);
	 cout<<dp[k-1];
	
	 //system("pause");
	 return 0;
	}

	
	
	
	
	/**************************************
	 Problem id : SDUT OJ 1898
	 User name : 電泡泡
	 Result : Time Limit Exceeded
	 Take Memory : 0K
	 Take Time : 1010MS
	 Submit Time : 2013-05-06 08:01:39
	**************************************/
	#include <iostream>
	#include <algorithm>
	#include <stdio.h>
	using namespace std;

	int a[10000], dp[10000], k=0, n;

	void
	ul(int n)
	{
	 int i;
	 for(i=1; i*i<n; i++){
	
	 if(0==n%i){
	 a[k++]=i;
	 a[k++]=n/i;
	 }
	 }
	 if(i*i==n)
	 a[k++]=i;
	}

	void
	solve(int n)
	{
	 int i, j;
	 dp[0]=1;
	 for(i=1; i<k; i++){
	 dp[i]=0;
	 for(j=0; j<i; j++)
	 if(a[i]%a[j]==0)
	 dp[i]+=dp[j];
	 }
	}

	int
	main()
	{
	 cin>>n;
	 ul(n);
	 sort(a, a+k);
	 solve(n);
	 cout<<dp[k-1];
	
	 //system("pause");
	 return 0;
	}





	/**************************************
	 Problem id : SDUT OJ 1898
	 User name : 電泡泡
	 Result : Accepted
	 Take Memory : 472K
	 Take Time : 0MS
	 Submit Time : 2013-05-06 10:47:03
	**************************************/

试试其它关键字

　整數因子　

同语言下

可能有用的

電泡泡贡献的其它代码(2)