|
|
題目鏈接： http://poj.org/problem?id=3489
  /**//*
 題意：
給定n( n <= 1000 )個(gè)大小為Vi的物品，每個(gè)物品都可以拆分成k次，拆分好的
物品可以繼續(xù)拆分，Vi是整數(shù)，但是拆分好的物品的大小可以是任意實(shí)數(shù)，例如本來
Vi為7的物品拆分成5份，那么每份大小就是1.4，問最后能不能通過拆分和組合組出
大小為x的物品（每個(gè)物品的供應(yīng)量是無窮多的）。
題解：
數(shù)學(xué)推導(dǎo)
思路：
問題求得就是以下方程有沒有整數(shù)解：
x1*V1/(k^y1) + x2*V2/(k^y2) +  + xn*Vn/(k^yn) = x
其中x1，y1是未知量。首先要明確的一點(diǎn)是，一個(gè)物品可以拆分的無限小，也就是
k^yi可以很大很大，因?yàn)楫?dāng)k^yi取得越大時(shí)，我們總可以找到k^yi個(gè)這類物品把它
還原成原來的大小，所以不影響解題；相反，如果取得比較小的話可能找不到可行
解，因?yàn)檫€沒有達(dá)到要拆分的次數(shù)，然后我們這樣考慮，令G = gcd(V1, V2 )
，并且Ti = Vi / G。那么原方程就可以表示成如下形式：
G * ( x1*T1/(k^y1) + x2*T2/(k^y2) + + xn*Tn/(k^yn) ) = x
然后令M = k^j，你可以假設(shè)這個(gè)M足夠大。再將上面的方程變形：
S = x1*T1*(k^(j-y1)) + x2*T2*(k^(j-y2)) + + xn*Tn/(k^(j-yn));
G / M * S = x
接下啦，如果在G中的素因子同時(shí)存在于k中，那么我們把這些素因子全部剔除
，這一步其實(shí)就是求G和M的最大公約數(shù)，這就是為什么M要取足夠大的原因。方程
轉(zhuǎn)變成：
G' = G / gcd(G, M);
M' = M / gcd(G, M);
G' / M' * S = x;
然后我們將等式兩邊都乘上M'，可以得到：
G'* S = x * M';
這四個(gè)數(shù)都是整數(shù)，G'和M'互質(zhì)，所以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的情況，我們?nèi)∪我鈨煞N物品，其他物品假設(shè)都不取，如果這樣都
能組合出來，那么結(jié)論就顯然了。來看下面的方程：
A = x1*T1*(k^(j-y1));
B = x2*T2*(k^(j-y2));
A + B = x' * M';
于是問題就轉(zhuǎn)變成了線性同余方程是否有整數(shù)解的問題了。
不妨假設(shè)y1 < y2，那么GG = gcd(A, B) = k^(j-y2);因?yàn)閥1和y2的各自取值不
影響最后結(jié)果（因?yàn)榭捎煤芏鄠€(gè)x2來補(bǔ)充），我們可以大膽的將y2取值為j。于是GG
就等于1了。這樣方程就必然有解了。
結(jié)論得證。
 */
#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;
}
|