Autor da análise: tmadeira
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1395
Resumo
(Essa explicação só funciona pois os testes dos juízes estão fracos!)
É dado um conjunto $A = \{ a_1, a_2, ..., a_n \} \subset \mathbb{Z}$ de $n$ elementos assumindo valores de 1 a 20 (na verdade os elementos vão de 5 a 100, mas há um menor elemento $m$ que divide todos os outros, então dividindo todos os números por $m$ obtem-se este conjunto com elementos de 1 a 20).
O problema é, dado um número racional $\frac{p}{q}$ ($1 \leq p, q \leq 10000$), determinar se ele pode ser escrito como produto dos números do conjunto $A$, i.e., determinar se existem $e_i \in \mathbb{Z}$ (i = 1, 2, …, n), tais que $\displaystyle \frac{p}{q} = \Pi_{i = 1}^{n} a_i^{e_i}$
Solução
Primeiramente removemos fatores repetidos. Para cada par $a_i, a_j$ de números do conjunto A, se $a_j | a_i$ então $a_i = \frac{a_i}{a_j}$. O motivo disto é que $\frac{a_i}{a_j}$ e os números que possuem ele e qualquer outro inteiro de A como fatores podem ser feitas. Por exemplo, se $A = \{ 1, 2, 6 \}$, eu consigo fazer $\frac{1}{3} = \frac{2}{6}$, $\frac{1}{3^2} = \frac{2^2}{6^2}$, $\frac{1}{3^3} = \frac{2^3}{6^3}$, etc.
Então criamos um vetor $M$ de 10000 posições, tal que $M_i = 1$ se e somente se é possível escrever $i$ como a multiplicação de números de $A$ por outros números que é possível escrever (senão, $M_i = 0$).
Para preencher esse vetor, iniciamos com $M_1 = 1$ e para cada número $i$ já marcado (por ordem crescente), marcamos $i \cdot A_j$ ($j = 1, 2, ..., n$).
(marcar $u$ significa realizar a atribuição $M_u = 1$).
Agora, dado o racional $\frac{p}{q}$, basta tirar o MDC entre $p, q$ e dividir ambos pelo MDC (para ter a fração reduzida) e então testar $\forall k >= 0$ (enquanto $p \cdot k, c \cdot k \leq 10000$) se $p \cdot k$ e $q \cdot k$ estão no conjunto. Se estiverem, este número pode ser feito.
Nota: Este $k$ é importante por causa do segundo cenário abaixo. Provavelmente há uma solução mais bonita (tirando MDCs ao processar cada par de números ou algo do gênero), mas essa funciona.
Testes
Entrada
2
3
7 14 42
3
2 6
1 7
1 6561
3
1 4 10
1
4 10
Saída
Scenario #1:
Gear ratio 2:6 can be realized.
Gear ratio 1:7 cannot be realized.
Gear ratio 1:6561 can be realized.
Scenario #2:
Gear ratio 4:10 can be realized.
Discuta o problema
1
3
5 30 45
1
4096 1
E ele tem razão, não? Teria algum motivo pra dar errado?
Depois de dividir tudo pelo menor ficamos com engranagens de 6 e 9 e note que (6^12)/(9^6) = 4096, então a resposta deveria ser sim. Mas o seu algoritmo não acha porque o tamanho do vetor M é muito pequeno, nesse caso teria que ter pelo menos 6^12 = 2176782336 posições. Mas isso pede uma solução diferente dessa.
É verdade!
Outra entrada mal feita do juiz…
.
Seja $e_p(x)$ o expoente do primo $p$ na fatoração prima de $x$ e $p_k$ o $k$-ésimo primo (há $m=8$ deles de 1 a 20). Então existem valores $x_0,\cdots,x_{n-1}\in\mathbb Z$ tais que
(1)se, e somente se, o sistema de equações diofantinas lineares
(2)tiver solução, onde
(3)e
(4)Alguém aí sabe determinar a existência de solução de sistema de equações diofantinas lineares?
Edit: Na verdade também temos que exigir que $e_{x}(p) = e_{x}(q)$ para todo primo $x>19$.
Eu cheguei nisso que vc chegou.
Mas vc pode generalizar um pouco mais eu não precisa se limitar a equações difantinas e vc vai ter um sistema de equações lineares e vc quer saber se esse sistema possui soluções inteira.
Se tiver uma equação eu sei resolver, é só verificar se o mdc dos coeficientes das variáves divide o termo independente. Mas se tem mais de uma equação, eu não sei como faz…
Hum, talvez eu tenha usado a terminologia errada, mas sim, é isso que eu quero dizer, saber se um sistema linear com coeficientes inteiros tem solução inteira. Eu também sei fazer para uma variável. Eu procurei no Google e só achei coisas realmente complexas. Acho que vou dar um pulo no depto de matemática essa semana.