第一问答案显然是 $1$，考虑一下 $\mu$ 的计算过程就会发现平方数的 $\mu$ 是 $0$……。
$\varphi(i^2)=i \varphi(i)$ 这个也很显然，考虑一下欧拉函数的计算式就知道是对的了。
然后就是杜教筛。
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
| #include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, pri[1000005], cnt, phi[1000005];
bool isp[1000005];
const int mod=1e9+7, mo=1000003;
struct HashTable{
int hea[1000005], cnt;
struct Edge{
int x, y, nxt;
}edge[1000005];
void add(int x, int y){
int p=x%mo;
edge[++cnt].x = x; edge[cnt].y = y; edge[cnt].nxt = hea[p];
hea[p] = cnt;
}
int getV(int x){
int p=x%mo;
for(int i=hea[p]; i; i=edge[i].nxt)
if(edge[i].x==x)
return edge[i].y;
return 0;
}
}hst;
int F(int x){
if(x<=1000000) return phi[x];
int t=hst.getV(x);
if(t) return t;
int re=0, lst;
for(int i=2; i<=x; i=lst+1){
lst = x / (x / i);
re = (re + (ll)F(x/i)*(i+lst)%mod*(lst-i+1)%mod*500000004%mod) % mod;
}
re = ((ll)x*(x+1)%mod*(2*x%mod+1)%mod*166666668%mod - re + mod) % mod;
hst.add(x, re);
return re;
}
int main(){
cin>>n;
memset(isp, true, sizeof(isp));
isp[0] = isp[1] = true; phi[1] = 1;
for(int i=2; i<=1000000; i++){
if(isp[i]) pri[++cnt] = i, phi[i] = i - 1;
for(int j=1; j<=cnt && i*pri[j]<=1000000; j++){
isp[i*pri[j]] = false;
if(i%pri[j]==0){
phi[i*pri[j]] = phi[i] * pri[j];
break;
}
else phi[i*pri[j]] = phi[i] * (pri[j] - 1);
}
}
for(int i=2; i<=1000000; i++)
phi[i] = (phi[i-1] + (ll)i * phi[i] % mod) % mod;
cout<<1<<"\n"<<F(n)<<endl;
return 0;
}
|