首页 > 代码库 > BestCoder Round #6(1003)hdu4983(欧拉函数)

BestCoder Round #6(1003)hdu4983(欧拉函数)

Goffi and GCD


Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 412    Accepted Submission(s): 34


Problem Description
Goffi is doing his math homework and he finds an equality on his text book: gcd(n?a,n)×gcd(n?b,n)=nk.

Goffi wants to know the number of (a,b) satisfy the equality, if n and k are given and 1a,bn.

Note: gcd(a,b) means greatest common divisor of a and b.
 
Input
Input contains multiple test cases (less than 100). For each test case, there‘s one line containing two integers n and k (1n,k109).
 
Output
For each test case, output a single integer indicating the number of (a,b) modulo 109+7.
 
Sample Input
2 1 3 2
 
Sample Output
2 1
Hint
For the first case, (2, 1) and (1, 2) satisfy the equality.

题意:RT

思路:很容易看出k>2时无解,k=2时一个解,k=1时可以预处理出G(x),表示gcd(i,n)=x的i的个数,这里求G(x)等价于求小于n/x且与之互素的数的个数,然后最后累加

            G(x)*G(n/x)即可,其中x是n的因子

<script src="https://code.csdn.net/snippets/457970.js" type="text/javascript"></script>

BestCoder Round #6(1003)hdu4983(欧拉函数)