首页 > 代码库 > 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 DescriptionGoffi 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 1≤a,b≤n .
Note: gcd(a,b) means greatest common divisor of a and b .
InputInput contains multiple test cases (less than 100). For each test case, there‘s one line containing two integers n and k (1≤n,k≤109 ).
OutputFor each test case, output a single integer indicating the number of (a,b ) modulo 109+7 .
Sample Input2 1
3 2
Sample Output2
1
Hint
For the first case, (2, 1) and (1, 2) satisfy the equality.
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, ifn andk are given and1≤a,b≤n .
Note:gcd(a,b) means greatest common divisor ofa andb .
Input contains multiple test cases (less than 100). For each test case, there‘s one line containing two integersn andk (1≤n,k≤109 ).
For each test case, output a single integer indicating the number of (a,b ) modulo109+7 .
2 1 3 2
2 1HintFor 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（欧拉函数）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。