PKU 3489 Knapsack I
英雄哪里出来发表于 2011-04-15 04:03:00
题目链接：http://poj.org/problem?id=3489
/**//*
题意：
给定n( n <= 1000 )个大小为Vi的物品，每个物品都可以拆分成k次，拆分好的
物品可以继续拆分，Vi是整数，但是拆分好的物品的大小可以是任意实数，例如本来
Vi为7的物品拆分成5份，那么每份大小就是1.4，问最后能不能通过拆分和组合组出
大小为x的物品（每个物品的供应量是无穷多的）。
题解：
数学推导
思路：
问题求得就是以下方程有没有整数解：
x1*V1/(k^y1) + x2*V2/(k^y2) + 
+ xn*Vn/(k^yn) = x
其中x1，y1是未知量。首先要明确的一点是，一个物品可以拆分的无限小，也就是
k^yi可以很大很大，因为当k^yi取得越大时，我们总可以找到k^yi个这类物品把它
还原成原来的大小，所以不影响解题；相反，如果取得比较小的话可能找不到可行
解，因为还没有达到要拆分的次数，然后我们这样考虑，令G = gcd(V1, V2 )
，并且Ti = Vi / G。那么原方程就可以表示成如下形式：
G * ( x1*T1/(k^y1) + x2*T2/(k^y2) + + xn*Tn/(k^yn) ) = x
然后令M = k^j，你可以假设这个M足够大。再将上面的方程变形：
S = x1*T1*(k^(j-y1)) + x2*T2*(k^(j-y2)) + + xn*Tn/(k^(j-yn));
G / M * S = x
接下啦，如果在G中的素因子同时存在于k中，那么我们把这些素因子全部剔除
，这一步其实就是求G和M的最大公约数，这就是为什么M要取足够大的原因。方程
转变成：
G' = G / gcd(G, M);
M' = M / gcd(G, M);
G' / M' * S = x;
然后我们将等式两边都乘上M'，可以得到：
G'* S = x * M';
这四个数都是整数，G'和M'互质，所以G'必然要整除x，否则方程无解。那么
接下来就是要看，如果整除的话是否一定有解。
令x' = x / G'; 那么有S = x' * M';
首先考虑n = 1的情况，如果n = 1，那么x1*(k^(j-y1)) = x' * M';我们只要
取x1 = x' * M'，y1 = j 就可以了。
然后是n > 1的情况，我们取任意两种物品，其他物品假设都不取，如果这样都
能组合出来，那么结论就显然了。来看下面的方程：
A = x1*T1*(k^(j-y1));
B = x2*T2*(k^(j-y2));
A + B = x' * M';
于是问题就转变成了线性同余方程是否有整数解的问题了。
不妨假设y1 < y2，那么GG = gcd(A, B) = k^(j-y2);因为y1和y2的各自取值不
影响最后结果（因为可用很多个x2来补充），我们可以大胆的将y2取值为j。于是GG
就等于1了。这样方程就必然有解了。
结论得证。
*/
#include <iostream>
#include <vector>
#include <vector>
using namespace std;
#define maxn 65537
bool f[maxn];
int prime[maxn], size;
int gcd(int a, int b) {
return b==0 ? a : gcd(b, a%b);
}
void Divide(vector<int>& ans, int v) {
ans.clear();
if(v == 1)
return ;
int i;
for(i = 0; i < size; i++) {
if(v % prime[i] == 0) {
while(v % prime[i] == 0)
v /= prime[i];
ans.push_back(prime[i]);
if(v == 1)
return ;
}
}
ans.push_back(v);
}
int n, x, k;
int main() {
int i, j;
for(i = 2; i < maxn; i++) {
if(!f[i]) {
prime[size++] = i;
for(j = i+i; j < maxn; j += i) {
f[j] = 1;
}
}
}
while(scanf("%d %d %d", &n, &x, &k) != EOF) {
int G = 0;
for(i = 0; i < n; i++) {
int val;
scanf("%d", &val);
if(i)
G = gcd(G, val);
else
G = val;
}
vector<int> vecG;
vector<int> vecK;
Divide(vecG, G);
Divide(vecK, k);
bool flag = false;
for(i = 0; i < vecG.size(); i++) {
for(j = 0; j < vecK.size(); j++) {
if(vecG[i] == vecK[j])
break;
}
if(j == vecK.size()) {
while(G % vecG[i] == 0) {
G /= vecG[i];
if(x % vecG[i] == 0)
x /= vecG[i];
else {
flag = true;
break;
}
}
if(flag)
break;
}
}
printf("%s\n", flag ? "No" : "Yes");
}
return 0;
}
/**//*题意： 给定n( n <= 1000 )个大小为Vi的物品，每个物品都可以拆分成k次，拆分好的物品可以继续拆分，Vi是整数，但是拆分好的物品的大小可以是任意实数，例如本来Vi为7的物品拆分成5份，那么每份大小就是1.4，问最后能不能通过拆分和组合组出大小为x的物品（每个物品的供应量是无穷多的）。题解： 数学推导思路： 问题求得就是以下方程有没有整数解： x1*V1/(k^y1) + x2*V2/(k^y2) + + xn*Vn/(k^yn) = x其中x1，y1是未知量。首先要明确的一点是，一个物品可以拆分的无限小，也就是k^yi可以很大很大，因为当k^yi取得越大时，我们总可以找到k^yi个这类物品把它还原成原来的大小，所以不影响解题；相反，如果取得比较小的话可能找不到可行解，因为还没有达到要拆分的次数，然后我们这样考虑，令G = gcd(V1, V2 )，并且Ti = Vi / G。那么原方程就可以表示成如下形式： G * ( x1*T1/(k^y1) + x2*T2/(k^y2) + + xn*Tn/(k^yn) ) = x 然后令M = k^j，你可以假设这个M足够大。再将上面的方程变形： S = x1*T1*(k^(j-y1)) + x2*T2*(k^(j-y2)) + + xn*Tn/(k^(j-yn)); G / M * S = x 接下啦，如果在G中的素因子同时存在于k中，那么我们把这些素因子全部剔除，这一步其实就是求G和M的最大公约数，这就是为什么M要取足够大的原因。方程转变成： G' = G / gcd(G, M); M' = M / gcd(G, M); G' / M' * S = x; 然后我们将等式两边都乘上M'，可以得到： G'* S = x * M'; 这四个数都是整数，G'和M'互质，所以G'必然要整除x，否则方程无解。那么接下来就是要看，如果整除的话是否一定有解。 令x' = x / G'; 那么有S = x' * M'; 首先考虑n = 1的情况，如果n = 1，那么x1*(k^(j-y1)) = x' * M';我们只要取x1 = x' * M'，y1 = j 就可以了。 然后是n > 1的情况，我们取任意两种物品，其他物品假设都不取，如果这样都能组合出来，那么结论就显然了。来看下面的方程： A = x1*T1*(k^(j-y1)); B = x2*T2*(k^(j-y2)); A + B = x' * M'; 于是问题就转变成了线性同余方程是否有整数解的问题了。 不妨假设y1 < y2，那么GG = gcd(A, B) = k^(j-y2);因为y1和y2的各自取值不影响最后结果（因为可用很多个x2来补充），我们可以大胆的将y2取值为j。于是GG就等于1了。这样方程就必然有解了。 结论得证。*/#include <iostream>#include <vector>#include <vector>using namespace std;#define maxn 65537bool f[maxn];int prime[maxn], size;int gcd(int a, int b) { return b==0 ? a : gcd(b, a%b);}void Divide(vector<int>& ans, int v) { ans.clear(); if(v == 1) return ; int i; for(i = 0; i < size; i++) { if(v % prime[i] == 0) { while(v % prime[i] == 0) v /= prime[i]; ans.push_back(prime[i]); if(v == 1) return ; } } ans.push_back(v);}int n, x, k;int main() { int i, j; for(i = 2; i < maxn; i++) { if(!f[i]) { prime[size++] = i; for(j = i+i; j < maxn; j += i) { f[j] = 1; } } } while(scanf("%d %d %d", &n, &x, &k) != EOF) { int G = 0; for(i = 0; i < n; i++) { int val; scanf("%d", &val); if(i) G = gcd(G, val); else G = val; } vector<int> vecG; vector<int> vecK; Divide(vecG, G); Divide(vecK, k); bool flag = false; for(i = 0; i < vecG.size(); i++) { for(j = 0; j < vecK.size(); j++) { if(vecG[i] == vecK[j]) break; } if(j == vecK.size()) { while(G % vecG[i] == 0) { G /= vecG[i]; if(x % vecG[i] == 0) x /= vecG[i]; else { flag = true; break; } } if(flag) break; } } printf("%s\n", flag ? "No" : "Yes"); } return 0;}