codeforces 594 D. REQ (树状数组+欧拉函数+逆元)

phi(n)是欧拉函数，意义为小于等于n并且与n互质的数的个数。

To calculate the answer on every query let’s use the formula , where p1, p2, …, pk — all prime numbers which dividedn.