Hi,
I have tried the following to solve this problem 833A - The Meaningless Game with the following approach.
- preprocessing: get all the prime numbers from 2 to the floor(square root of 10^9).
- for the input a and b, get their prime factorizations using the prime number list.
- do the following check:
3(a). check if both a and b's prime factorizations contain the same set of prime numbers, i.e, there is no prime number that only exists in one of the factorization but not the other.
3(b). if passing the above check, then for each prime number P that appears in the factorization, do the following check:
A few notes: Say P appears v1 times in a's factorization and v2 times in b's factorization.
Of all the times P appear in a round, assume the 1st player(Slastyona) wins c1 times and the 2nd player(her dog) wins c2 times, we then have:
c1 * 2 + c2 = v1
c1 + c2 * 2 = v2
from the above two equations, we have c2 = (v2 * 2 — v1) / 3, c1 = v2 — (v2 * 2 — v1) / 3 * 2. So we check if v2 * 2 — v1 >= 0 and is divisible by 3, we also check if c1 >= 0. If these conditions are all true, the check for the prime number P passes otherwise it fails.
Intuition:
The reason that I chose to use prime factorization is that each round if we are given a composite number k, we can convert it to a product of only prime numbers and use multiple rounds to get the same result. For example, if k is 6, then k^2 = 36, we can have 1 round of k = 2 and another round of k = 3 to get the same result.
The max prime number we need to consider is upper bounded by the square root of 10^9 since if there is prime factor that is bigger than this upper bound, then the winner of that round will multiply a number that is bigger than 10^9.
However, the above approach is incorrect and it fails on test case 4. Unfortunately I can not see the input that gives the wrong output. My submission link is 140311042
I think my approach is not correct but could not figure out why it is wrong, can some one help to provide some insights on why this gives the wrong answer?
Thanks!
