首页 > 代码库 > 整数划分问题

整数划分问题

2024-10-24 06:39:02   211人阅读

描述

Given two positive integers N and M, please divide N into several integers A1, A2, ..., Ak (k >= 1), so that:

1. 0 < A1 < A2 < ... < Ak;

2. A1 + A2 + ... + Ak = N;

3. A1, A2, ..., Ak are different with each other;

4. The product of them P = A1 * A2 * ... * Ak is a multiple of M;

How many different ways can you achieve this goal?

输入

Two integers N and M. 1 <= N <= 100, 1 <= M <= 50.

输出

Output one integer -- the number of different ways to achieve this goal, module 1,000,000,007.

样例提示

There are 4 different ways to achieve this goal for the sample:

A1=1, A2=2, A3=4;

A1=1, A2=6;

A1=2, A2=5;

A1=3, A2=4.

样例输入
7 2
样例输出
4
#include <iostream>
using namespace std;
int N=0;
//用于打印(输出)的函数
//result为存储某划分结果的数组，length为此划分所占长度-1（从0开始）
void display(int *result,int length)       
{	
	for(int i=0;i<length;i++)
		cout<<result[i]<<" ";
	cout<<endl;
}

bool noRepeat(int *result,int length){
	int a[1000]={0};
	for(int i=0;i<length;i++){
		if(a[result[i]]!=0){
			return false;
		}
		else{
			a[result[i]]++;
		}
	}
	return true;
}
bool isMultipleRight(int *result,int length,int m){
	int a=1;
	for(int i=0;i<length;i++){
		a*=result[i];
	}
	if(a%m == 0){
		return true;
	}
	return false;
}
//主划分函数q(int n,int m,int *result,int length)
//n为待划分整数，m为最大加数上限,result和length意以同display函数
//将q分成五种情况分类讨论，其中包含递归调用
int q(int n,int m,int *result,int length,int multiple)
{
//当n>=1并且m=1时，q(n,m,result,length)=q(n-1,m,result,length)	
	 if(n>=0&&m==1)                    	                                                               
	{
		//直至n=0并且m=1时，输出
		if(n==0)
		{
			display(result,length);
			if(noRepeat(result,length)&&isMultipleRight(result,length,multiple)){
				N++;
			}
		}	
		else
		{
			result[length]=1;
			q(n-1,m,result,length+1,multiple);
		}
		return 1;
	}


// 当 n=1并且m>1 时，分解已经完成，进行输出
	else if(n==1&&m>1)                               
	{
		result[length]=n;
		display(result,length+1);
		if(noRepeat(result,length)&&isMultipleRight(result,length,multiple)){
				N++;
		}
		return 1;
	}

//当n<m时，q(n,m,result,length)=q(n,n,result,length)
	else if(n<m)                                      
   {
		return q(n,n,result,length,multiple);
	}

//当n=m时，q(n,m,result,length)=q(n,m-1,result,length)+1（划分数目）
	else if(n==m)                                         
{
		result[length]=m;
		display(result,length+1);
		if(noRepeat(result,length)&&isMultipleRight(result,length,multiple)){
				N++;
		}
		return q(n,m-1,result,length,multiple)+1;
	}

//当n>m>1时，//q(n,m,result,length)=q(n-m,m,result,length+1)+q(n,m-1,result,length)
	else                                                         
	{
		result[length]=m;
	    return q(n-m,m,result,length+1,multiple)+q(n,m-1,result,length,multiple);
	}
}


int main()
  {
	  int n,m;                            
	  int result[100]={0},length=0;
	  cout<<"please input the integer:";  
	  cin>>n>>m;
	  cout<<"整数"<<n<<"的划分个数为"<<q(n,n,result,length,m)<<endl;
	  cout<<"合格的划分个数是"<<N<<endl; 
	  return 0;
  }


整数划分问题


联系
我们