Problem E. GuGuFishtion

时间限制 1500 ms   内存限制 64 MB

Today XianYu is too busy with his homework, but the boring GuGu is still disturbing him!!!!!!
At the break time, an evil idea arises in XianYu's mind.
‘Come on, you xxxxxxx little guy.’
‘I will give you a function $\phi(x)$ which counts the positive integers up to $x$ that are relatively prime to $x$.’
‘And now I give you a fishtion, which named GuGu Fishtion, in memory of a great guy named XianYu and a disturbing and pitiful guy GuGu who will be cooked without solving my problem in 5 hours.’
‘The given fishtion is defined as follow:
$$G_u (a,b)=\frac{\phi(ab)}{\phi(a)\phi(b)}$$
And now you, the xxxxxxx little guy, have to solve the problem below given $m$,$n$,$p$.’
$$(\sum\limits_{a=1}^m\sum\limits_{b=1}^nG_u (a,b))\pmod p$$
So SMART and KINDHEARTED you are, so could you please help GuGu to solve this problem?
‘GU GU!’ GuGu thanks.
 

输入数据

Input contains an integer $T$ indicating the number of cases, followed by $T$ lines. Each line contains three integers $m$,$n$,$p$ as described above.
$1\le T\le 3$
$1\le m,n\le 1,000,000$
$\max(m,n)<p\le 1,000,000,007$
And given $p$ is a prime.
 

输出数据

Please output exactly $T$ lines and each line contains only one integer representing the answer.
 

样例输入

复制
1
5 7 23

样例输出

提交

请先 登录

© 2025 FAQs Contact About