首页 > 代码库 > Math Magic（完全背包）
Math Magic（完全背包）
Math Magic
Time Limit:3000MS Memory Limit:32768KB 64bit IO Format:%lld & %lluDescription
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 23 2 2
Sample Output
12
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 1000000007int num[1000];int dp[2][1010][1010];int LCM[1010][1010];int gcd(int a,int b)//最大公约数{ if(b==0) 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=1;i<=1000;i++)//预处理，前1000的最小公倍数 { for(j=1;j<=1000;j++) { LCM[i][j]=lcm(i,j); } } while(scanf("%d%d%d",&n,&m,&k)!=EOF) { int cnt=0; //因为最小公倍数m已知，所以Ai必定是他的因子 for(i=1;i<=m;i++) { if(m%i==0) num[cnt++]=i; } //dp[now][i][j]now表示当前状态下，和为i,最小公倍数为j的解的个数。递推K次就出答案了。 int now=0; //memset(dp[nom],0,sizeof(dp[nom])); for(i=0;i<=n;i++) { for(j=0;j<cnt;j++) { //初始化，和为i，最小公倍数是num[j]的 dp[now][i][num[j]]=0; } } dp[0][0][1]=1; for(int t=1;t<=k;t++) { now^=1; for(i=0;i<=n;i++) { for(j=0;j<cnt;j++) { dp[now][i][num[j]]=0; } } for(i=t-1;i<=n;i++) { for(j=0;j<cnt;j++) { if(dp[now^1][i][num[j]]==0)continue; for(int p=0;p<cnt;p++) { int x=i+num[p]; int y=LCM[num[j]][num[p]]; if(x>n||m%y!=0) continue; dp[now][x][y]+=dp[now^1][i][num[j]]; dp[now][x][y]%=mod; } } } } printf("%d\n",dp[now][n][m]); } return 0;}
Math Magic（完全背包）