Description
Yesterday, my teacher taught us about math: +, -, *, /, GCD, LCM... As you know, LCM (Least common multiple) of two positive numbers can be solved easily because of a * b = GCD (a, b) * LCM (a, b).
In class, I raised a new idea: "how to calculate the LCM of K numbers". It's also an easy problem indeed, which only cost me 1 minute to solve it. I raised my hand and told teacher about my outstanding algorithm. Teacher just smiled and smiled...
After class, my teacher gave me a new problem and he wanted me solve it in 1 minute, too. If we know three parameters N, M, K, and two equations:
1. SUM (A1, A2, ..., Ai, Ai+1,..., AK) = N
2. LCM (A1, A2, ..., Ai, Ai+1,..., AK) = M
Can you calculate how many kinds of solutions are there for Ai (Ai are all positive numbers). I began to roll cold sweat but teacher just smiled and smiled.
Can you solve this problem in 1 minute?
Input
There are multiple test cases.
Each test case contains three integers N, M, K. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ 100)
Output
For each test case, output an integer indicating the number of solution modulo 1,000,000,007(1e9 + 7).
You can get more details in the sample and hint below.
Sample Input
4 2 2
3 2 2
Sample Output
1
2
Hint
The first test case: the only solution is (2, 2).
The second test case: the solution are (1, 2) and (2, 1).
题意：
给出n,m,k,问k个数的和为n，最小公倍数为m的情况有几种
思路：
因为最小公倍数为m，可以知道这些数必然是m的因子，那么我们只需要选出这所有的因子，拿这些因子来背包就可以了
dp[now][i][j]表示当前状态下，和为i，最小公倍数为j的解的个数。递推K次就出答案了。
注意需要优化！！！
详见代码
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define mod 1000000007 int num[];
int dp[][][];
int LCM[][]; int gcd(int a,int b)//最大公约数
{
if(b==) return a;
return gcd(b,a%b);
} int lcm(int a,int b)//最小公倍数
{
return (a*b/gcd(a,b));
} int main()
{
int n,m,k;
int i,j;
for(i=;i<=;i++)//预处理，前1000的最小公倍数
{
for(j=;j<=;j++)
{
LCM[i][j]=lcm(i,j);
}
}
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
int cnt=;
//因为最小公倍数m已知，所以Ai必定是他的因子
for(i=;i<=m;i++)
{
if(m%i==)
num[cnt++]=i;
} //dp[now][i][j]now表示当前状态下，和为i,最小公倍数为j的解的个数。递推K次就出答案了。
int now=;
//memset(dp[nom],0,sizeof(dp[nom]));
for(i=;i<=n;i++)
{
for(j=;j<cnt;j++)
{
//初始化，和为i，最小公倍数是num[j]的
dp[now][i][num[j]]=;
}
}
dp[][][]=; for(int t=;t<=k;t++)
{
now^=;
for(i=;i<=n;i++)
{
for(j=;j<cnt;j++)
{
dp[now][i][num[j]]=;
}
} for(i=t-;i<=n;i++)
{
for(j=;j<cnt;j++)
{
if(dp[now^][i][num[j]]==)continue;
for(int p=;p<cnt;p++)
{
int x=i+num[p];
int y=LCM[num[j]][num[p]];
if(x>n||m%y!=) continue;
dp[now][x][y]+=dp[now^][i][num[j]];
dp[now][x][y]%=mod;
}
}
}
}
printf("%d\n",dp[now][n][m]);
}
return ;
}