Hi,↵
↵
I have tried the following to solve this problem [problem:833A] with the following approach.↵
↵
1. preprocessing: get all the prime numbers from 2 to the floor(square root of 10^9). ↵
2. for the input a and b, get their prime factorizations using the prime number list.↵
3. 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:↵
↵
1. 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.↵
↵
2. 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 [submission: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!
↵
I have tried the following to solve this problem [problem:833A] with the following approach.↵
↵
1. preprocessing: get all the prime numbers from 2 to the floor(square root of 10^9). ↵
2. for the input a and b, get their prime factorizations using the prime number list.↵
3. 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:↵
↵
1. 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.↵
↵
2. 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 [submission: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!
