Problem 1541 --最大公约数

1541: 最大公约数

上一题 正确率: $75.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $4$ 正确数量 $3$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

有这样一个有关最大公约数的函数:
函数 f(x, y):
{
     c=0
     当 y>0:
     {
          c +=1
          t = x % y
          x = y
          y = t
      }
      返回 c * x * x
}

给出三个正整数n,m,p，你需要计算:


对p取模的结果。
 

Input

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

Output

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

Sample Input复制

3
10 5 23333
100 10 23333
1000 20 23333

Sample Output复制

271
22359
10998

推荐代码 查看1541 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$0 $ms] 沈伟 618214 2020-10-11 19:12:32
内存最少[$1156 $KB] 沈伟 618214 2020-10-11 19:12:32
第一AC AOJ大管家 435569 2019-05-31 00:12:48
第一挑战 史乐军@计算机科学与技术173 242878 2018-05-10 15:28:00

赛题来源/所属竞赛 2016年中国大学生程序设计竞赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛