mathematical programming – Four functions problem

This is not from online contest

Hi guys, a friend of mine recently give me this problem that I couldn’t figure out an effective way to solve it.

enter image description here

Here’s my observation:

  • About the constraints, there are 10^6 test cases, each test case can be as large as 10^6, I estimate we need an algorithm that is at least O(nlogn). Otherwise we will have TLE.

  • I guess this problem is a math one. We somehow need to come up with an efficient formula to resolve all 4 functions.

  • I know for sure if we solve this problem naively, we cannot pass all test cases. Even if we use the best method to compute gcd and prime factor.

  • I’ve thought about this one for two days I can’t find an acceptable solution for this problem. You can assume that this problem have time limit of 5 seconds.

Since this is a math problem, some talented and gifted genius out there might be interested. 😀

Please help to come up with a formula to solve this, or provide an understandable solution. Thank you very much.