题目
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 1≤a,b≤n.
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 (1≤n,k≤109).
Output
For each test case, output a single integer indicating the number of (a,b) modulo 109+7.
Simple input
2 1
3 2
Simple output
2
1
题目分析
进行分析，当n=1的时候不论k为多少，答案始终都只有一个解；当k>2的时候，最大公约数的乘机即AB=nn是不可能等于n^k的。当k=2时，A=N,B=N即可，所以我们只需要分析k=1的情况就好。
当k=1的时候，gcd(n-a,n)gcd(n-b,n)=nj也就是等价于gcd(a,n)gcd(b,n)=n;也就是说此时的gcd(a,n)是n的一个约数，那么直接对其进行暴力即可，求有多少个数与n的最大公约数为g即求欧拉函数的n/g
最后将求出的数字加和
AC代码
1567K/46MS1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
void fre()
{
freopen("c://test//input.in", "r", stdin);
freopen("c://test//output.out", "w", stdout);
}
#define MP(x,y) make_pair(x,y)
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
#define debug puts("----------")
#define INF 0x3f3f3f3f
#define maxn 1050
const long long mod = 1e9+7;
using namespace std;
long long euler(long long x)
{
long long i,res=x;
for(i=2;i*i<=x;i++)
{
if(x%i==0)
{
res=res/i*(i-1);
while(x%i==0)
x=x/i;
}
}
if(x>1)
res=res/x*(x-1);
return res;
}
int main()
{
int n,k;
while(scanf("%d%d",&n,&k)!=EOF)
{
if(n==1)
{
printf("1\n");
continue;
}
if(k==2)
{
printf("1\n");
continue;
}
if(k>2)
{
printf("0\n");
continue;
}
long long ans=0;
for(int i=1;i*i<=n;i++)
{
if(n%i==0)
{
if(n/i!=i)
{
ans+=(euler(i)%mod*euler(n/i)%mod*2)%mod;
}
else ans+=(euler(i)%mod*euler(n/i)%mod)%mod;
ans=ans%mod;
}
}
printf("%lld\n",ans);
}
}