随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

PKU 3489 Knapsack I

题目链接: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;
}

posted on 2011-04-15 12:03 英雄哪里出来 阅读(406) 评论(0)  编辑 收藏 引用 所属分类: 数学


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理