最大公约数

TimeLimit:3000MS MemoryLimit:65536KB

64-bit integer IO format:%I64d

未提交 | 登录后收藏

Problem Description

有这样一个有关最大公约数的函数:
函数 f(x, y):


{
     c=0
     当 y>0:
     {
          c +=1
          t = x % y
          x = y
          y = t
      }
      返回 c * x * x
}

给出三个正整数n,m,p，你需要计算:
$$\sum_{i=1}^{n}\sum_{j=1}^{m} \lfloor \frac{i*j}{f(i,j)}\rfloor$$
对p取模的结果。

Input

包含多组测试数据。
第一行有一个正整数，表示数据的组数。
接下来每行表示一组数据，这一行有三个空格隔开的正整数n,m,p。
保证 n <= 666,666,666, m <= 666, p <= 666,666,666。
最终的测试数据中共有66组数据，并且每一个n,m,p都是在上述范围内均匀随机生成的。

Output

对于每个输入数据输出一行，这一行只包含一个整数即答案。

SampleInput

3
10 5 23333
100 10 23333
1000 20 23333

SampleOutput

271
22359
10998

Submit

题目统计信息详细


总AC数	1
通过人数	1
尝试人数	3
总提交量	5
AC率	20.00%

标签——3029

name	rating
数论	1017

AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题，请不要查看标签
如果您已经通过了该题，请务为该题贴上标签

出处

【每日一题】2018年5月

最大公约数

T^T Online Judge