#P18597. Euclidean Algorithm
Euclidean Algorithm
Euclidean Algorithm
题目描述
考试时,你试图回想最大公约数的算法。你记得 是同时整除 的最大正整数,却忘记了课堂上的其他内容。模糊的记忆让你设计出如下算法。
最初黑板上写着两个正整数 。每一步可以选择两个已经写在黑板上的数 ,计算
仅当 时,才可以把 也写到黑板上,原有数字仍然保留。
对数对 ,你把经过任意多次操作(也可以不操作)能够写出的最小正整数,作为算法的结果。
例如,初始为 时,先写出 ,再写出 。可以证明无法写出 ,因此算法给出了正确的最大公约数。可是对 ,能得到的最小数是 ,真正的最大公约数却是 。
给定 ,求满足 且上述算法的结果恰好为 的数对 的数量。
特别地,若 ,也认为算法正确,因为 最初就写在黑板上。
输入格式
第一行一个整数 ,表示测试用例数。
接下来 行,每行一个整数 ,且 。
数据范围
每个输入文件都属于以下三组之一:
| 输入组 | 测试用例数 | 每个测试用例的范围 |
|---|---|---|
| 第一组 | ||
| 第二组 | ||
| 第三组 |
不能将这些限制合并为“任意 、任意 ”。
输出格式
对每个测试用例,输出一行一个整数,表示所求数对数量。
样例输入 1
3
2
5
14
样例输出 1
1
9
62