2015
07-16

# Math Magic

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 495    Accepted Submission(s): 210

Problem 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(109 + 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).


Source

Recommend
zhuyuanchen520

1,2。2,1。是不同的组合也就是说和排序有关。

dp[i][j][k]。表示长度为i。和为j。最小公倍数为k的方法数。

dp[i+1][j+a][lcm(a,k)]+=dp[i][j][k]。

lcm为最大公倍数。

x。那么这k个数肯定都是x的因子。所以先预处理出x的因子。这样就可以有效的减少枚举范围。还有memset要慎用尤其是在这种数量级下。

#include <iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
const int maxn=1010;
const int mod=1000000007;

int dp[2][maxn][maxn];
int lcm[maxn][maxn];//lcm[a][b]为a,b的最大公约数。
int fac[maxn];//存m的因子
int gcd(int a,int b)
{
int t;
while(b)
{
t=a%b;
a=b;
b=t;
}
return a;
}
int main()
{
int n,m,k,cnt,i,j,p,q,e,f,t,v,mul,tt;

for(i=1; i<maxn; i++)
for(j=i; j<maxn; j++)//预处理出任意两数的最大公倍数
lcm[i][j]=lcm[j][i]=i*j/gcd(i,j);
while(~scanf("%d%d%d",&n,&m,&k))
{
cnt=0;
for(i=1; i<=m; i++)
{
if(m%i==0)
fac[cnt++]=i;
}
v=0;
memset(dp,0,sizeof dp);//记得要初始化。wa了千百回。里面的初始化只初始化了部分
for(i=0; i<cnt; i++)
dp[v][fac[i]][fac[i]]=1;
for(i=1; i<k; i++) //len
{
for(e=i; e<=n; e++)//必须手动初始化。不然超时
for(f=0; f<cnt; f++)
dp[v^1][e][fac[f]]=0;
for(j=i; j<n; j++) //sum
{
for(p=0; p<cnt; p++) //mul
{
mul=fac[p];
if(!dp[v][j][mul])
continue;
for(q=0; q<cnt; q++) //a[i]
{
tt=j+fac[q];
if(tt>n)
break;
t=lcm[mul][fac[q]];
dp[v^1][tt][t]+=dp[v][j][mul];
dp[v^1][tt][t]%=mod;
}
}
}
v^=1;
}
printf("%d\n",dp[v][n][m]);
}
return 0;
}