Loj 6053 简单的函数

Posted on | Views:

min_25 筛 .

  • 除了 $2$ 之外的质数 $p$ 都是奇数, $f(p)=p-1$ ,而 $f(2)=3$ .
  • 把 $f(p)$ 都当成 $f(p)=p-1$ ,用 min_25 筛法来做.有 $2$ 就特判一下, $+2$ 就好了.
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=2e5+10;
const int P=1e9+7;
const int inv2=(P+1)>>1;
inline int add(ll a,ll b)
{
	a%=P;
	b%=P;
	return (a + b) % P;
}
inline int mul(ll a,ll b)
{
	a%=P;
	b%=P;
	return 1LL * a * b % P;
}
ll n,sqr,w[MAXN];
int cnt=0,ism[MAXN],sump[MAXN],m;
ll prime[MAXN];
ll id1[MAXN],id2[MAXN];
void init(int N)
{
	ism[1]=1;
	for(int i=2;i<=N;++i)
	{
		if(!ism[i])
		{
			prime[++cnt]=i;
			sump[cnt]=add(sump[cnt-1],i);
		}
		for(int j=1;j<=cnt && prime[j]*i<=N;++j)
		{
			ism[prime[j]*i]=1;
			if(i%prime[j]==0)
				break;
		}
	}
}
int h[MAXN],g[MAXN],ans;
int S(ll x,int y)
{
	if(x<=1 || prime[y]>x)
		return 0;
	int k=(x<=sqr)?id1[x]:id2[n/x];
	int res=add(g[k]-sump[y-1],y-h[k]-1);
	if(y==1)
		res+=2;
	for(int i=y;i<=cnt && 1LL*prime[i]*prime[i]<=x;++i)
	{
		ll pow1=prime[i],pow2=1LL*prime[i]*prime[i];
		for(int e=1;pow2<=x;++e,pow1=pow2,pow2*=prime[i])
		{
			int tmp=mul(S(x/pow1,i+1),prime[i]^e);
			tmp=add(tmp,prime[i]^(e+1));
			res=add(res,tmp);
		}
	}
	return res;
}
int main()
{
	n=read();
	sqr=sqrt(n);
	init(sqr);
	for(ll l=1,r;l<=n;l=r+1)
	{
		ll &i=l,&j=r;
		r=n/(n/l);
		w[++m]=n/l;
		h[m]=add(w[m]%P,-1);
		g[m]=mul(w[m],w[m]+1);
		g[m]=mul(g[m],inv2);
		g[m]=add(g[m],-1);
		if(w[m]<=sqr)
			id1[n/l]=m;
		else
			id2[r]=m;
	}
	for(int j=1;j<=cnt;++j)
		for(int i=1;i<=m && prime[j]*prime[j]<=w[i];++i)
		{
			int k=(w[i]/prime[j]<=sqr)?id1[w[i]/prime[j]]:id2[n/(w[i]/prime[j])];
			g[i]=add(g[i],-mul(prime[j],add(g[k],-sump[j-1])));
			h[i]=add(h[i],j-h[k]-1);
		}
	ans=add(S(n,1),1);
	cout<<(ans+P)%P<<endl;
	return 0;
}