问题描述

C语言 这个好像很简单，但是怎写

Description

There are N stones in a circle, numbered from 0 to N-1. And there are k coins on the kth stone (For example, there are two coins on the stone with number 1). Now, Lasercat wants to collect as many coins as he can. However, he can leap over exactly L stones in a single step, which means he can jump from stone (j mod n) to stone ((j+L) mod n).

Lasercat starts from stone numbered 0 and he can jump as many times as he want. So how many coins can he collect in the end?

Input

The first line contain a single number C (1<=C<=1000) which means the number of test cases.
Then C lines follow, each line has two integers N(1<=N<=1000000) and L(1<=L<=1000000)

Output

For each test case, you should output two lines.
The first line is "Case #:", # means the number of the test case.
The second line output the number of the coins Lasercat can collect.

Sample Input
1
2 1

Sample Output
Case 1:
3

解决方案

你好像一直都在问问题，一边说好简单一边问那么多问题，你真的会吗？
好了，这个题很明显就是看Lx%N能取到哪些数。
看L和N的数据范围，有可能他们不互质，那么L/=gcd(L,N),N/=gcd(L,N)，那么接下来讨论L和N互质的情况。
L和N互质的时候，Lx%N只能取到N的简化剩余系里面的数。
N的简化剩余系元素之和是Nphi(N)/2.其中phi(N)是N的欧拉函数。
欧拉函数的求法就是分解质因数。
时间复杂度O(sqrt(N)).
记得最后的答案要乘回去gcd(L,N).
完了。