|
|
題目鏈接： 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;
}
|