[BZOJ 3512]DZY Loves Math IV

题目大意


思路

首先我们设

则所求

设x为n最大的无平方因子的约数

$y = \frac{n}{x}$ , 则 $\phi(ni) = y \cdot \phi(i) \cdot \phi(\frac{x}{gcd(x,i)}) \cdot gcd(x,i)$

由于x无平方因子,故

记忆化搜索


Code

1
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>
typedef long long LL;
#define N 1664512
#define U 1664510
#define MOD 1000000007
int n,m;
inline void mod(int &x){if(x >= MOD) x -= MOD;else if(x < 0) x += MOD;}
int vis[N],prime[N / 10],phi[N],pr[N],cnt;
void sieve(int n)
{
phi[1] = 1;pr[1] = 1;
for(int i = 2;i <= n;i++)
{
if(!vis[i]){prime[++cnt] = i;phi[i] = i - 1;pr[i] = i;}
for(int j = 1,k = i * prime[j];j <= cnt && i * (k = prime[j]) <= n;j++)
{
vis[i * k] = 1;
if(i % k)
{
phi[i * k] = phi[i] * phi[k];
pr[i * k] = pr[i] * k;
}
else
{
phi[i * k] = phi[i] * k;
pr[i * k] = pr[i];
break;
}
phi[i * k] = phi[i] * (k - 1);
pr[i * k] = pr[i] * k;
}
mod(phi[i] += phi[i - 1]);
}
}
namespace ha
{
const int p = 1001001;
struct eg{int n,v,t;}e[3000];
int cnt = 1,h[p];
inline void insert(int x,int val)
{
int u = x % p;
for(int i = h[u];i;i = e[i].n) if(e[i].t == x) return;
e[++cnt] = (eg){h[u],val,x};h[u] = cnt;
}
inline int query(int x)
{
int u = x % p;
for(int i = h[u];i;i = e[i].n) if(e[i].t == x) return e[i].v;
return -1;
}
}using ha::insert;using ha::query;
std::map<int,int> Map[N];
int pfx(int n)
{
if(n <= U) return phi[n];
int ret;if(~(ret = query(n))) return ret;
ret = ((LL) n * (n + 1) >> 1) % MOD;
int last;for(int i = 2;i <= n;i = last + 1)
{
last = n / (n / i);
mod(ret -= (LL) pfx(n / i) * (last - i + 1) % MOD);
}
insert(n,ret);return ret;
}
inline int qpow(int a,int b)
{
int ans = 1;
while(b)
{
if(b & 1) ans = ans * a;
a = a * a;
b >>= 1;
}
return ans;
}
inline LL PHI(int n)
{
int ans = 1;
if(n <= U){mod(ans = phi[n] - phi[n - 1]);return ans;}
int m = sqrt(n);
for(int i = 1;prime[i] <= m;i++) if(!(n % prime[i]))
{
int a = 0;while(!(n % prime[i])) a++,n /= prime[i];
ans *= qpow(prime[i],a - 1) * (prime[i] - 1);
}
return ans;
}
int S(int n,int m)
{
if(!m) return 0;
if(n == 1)return pfx(m);
if(Map[n][m]) return Map[n][m];
int ret = 0;
for(int i = 1;i * i <= n;i++) if(!(n % i))
{
int j = n / i;
mod(ret += PHI(j) * S(i,m / i) % MOD);
if(i != j) mod(ret += PHI(i) * S(j,m / j) % MOD);
}
return (Map[n][m] = ret);
}
int main()
{
sieve(U);
scanf("%d %d",&n,&m);
int ans = 0;
for(int i = 1;i <= n;i++) mod(ans += (LL) i / pr[i] * S(pr[i],m) % MOD);
printf("%d\n",ans);
return 0;
}