首页 > 代码库 > ZOJ3662:Math Magic(完全背包)
ZOJ3662:Math Magic(完全背包)
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
题意:
给出n,m,k,问k个数的和为n,最小公倍数为m的情况有几种
思路:
因为最小公倍数为m,可以知道这些数必然是m的因子,那么我们只需要选出这所有的因子,拿这些因子来背包就可以了
dp[i][j][k]表示放了i个数,和为j,公倍数为k的情况有几种
但是又问题,首先的问题内存,直接存明显爆内存,那么我们需要优化
1.因为我现在放第i个数,必然是根据放好的i-1个数来计算的,我们只需要用滚动数组来解决即可
2.对于公倍数,必然不能超过m,而我所有这些m的因子中的数字,无论选哪些,选多少,他们的最小公倍数依然是这些因子之中的,那么我们可以进行离散化
解决好了之后就是完全背包的问题了
#include <stdio.h> #include <algorithm> #include <string.h> #include <vector> #include <math.h> using namespace std; const int mod = 1e9+7; int dp[2][1005][105]; int a[1005],len,pos[1005]; int n,m,k; int hash[1005][1005]; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int lcm(int a,int b) { return a/gcd(a,b)*b; } int main() { int i,j,x,y; for(i = 1; i<=1000; i++)//预处理最小公倍数 { for(j = 1; j<=1000; j++) hash[i][j] = lcm(i,j); } while(~scanf("%d%d%d",&n,&m,&k)) { len = 0; memset(pos,-1,sizeof(pos)); for(i = 1; i<=m; i++) { if(m%i==0) { a[len] = i; pos[i] = len++;//离散化 } } memset(dp[0],-1,sizeof(dp[0])); dp[0][0][0] = 1; for(i = 1; i<=k; i++) { memset(dp[i%2],-1,sizeof(dp[i%2])); for(j = i-1; j<=n; j++)//因为最小必然放1,而我前面已经放了i-1个数了,前面的和最少必然是i-1 { for(x = 0; x<len; x++)//枚举前面数字的公倍数 { if(dp[(i+1)%2][j][x]==-1) continue; for(y = 0; y<len && (a[y]+j)<=n; y++)//枚举这一位放哪些数 { int r = hash[a[y]][a[x]]; int s = j+a[y]; if(pos[r]!=-1 && r<=m) { r = pos[r]; if(dp[i%2][s][r] == -1) dp[i%2][s][r] = 0; dp[i%2][s][r]+=dp[(i+1)%2][j][x]; dp[i%2][s][r]%=mod; } } } } } if(dp[k%2][n][pos[m]]==-1) printf("0\n"); else printf("%d\n",dp[k%2][n][pos[m]]); } return 0; }
ZOJ3662:Math Magic(完全背包)