Is there any min_25? I want to read the introduction of my uncle.
min_25 sieve is an integrative function prefix and algorithm developed by min_25, with a time complexity of\(O(\dfrac{n^{\frac 34}}{\log n})\)。
The scope of application of min_25 sieve is as follows:
- The requested function\(f(x)\)is an integral function.
- \(f(p^\alpha)\)Easy to solve, where\(p\)It's a prime number,\(\alpha\)It is a positive integer.
- \(f(p)\)It is easily expressed as the sum of multiple complete integrative functions.
So if you see a question, the description of the integrative function is\(f(p^\alpha)\)Based on it, it is very likely to be a min_25 screening board question.
min_25 sieve is named after the inventor's user name, but if it is from the perspective of algorithmic ideas, it belongs to\(dp\), also widely used the idea of Essai Sieve.
first step:\(g(n)=\sum\limits_{p\le n}f(p)\)
Let's just think about it first\(f(p)\)is a complete integrated function. If not, according to the requirements three, split it into multiple integrated functions and solve them separately and add them.
First sifting out\(\le\sqrt n+1\)All prime numbers are obviously not needed, because judging the prime numbers only requires\(\le\sqrt n\)Just scan all the prime numbers.
\(g(n)\)It is difficult to solve, consider the steps to decompose the EGYPT screen. We said before\(i\)The number of tests for prime numbers is\(i\)Level prime number, in the collection\(P_i\)middle. set up
\(G(i,j)=\sum\limits_{k\in P_j,k\le i}f(k)\), then there is\(g(i)=G(i,pr)\), among which\(pr\)The small prime number is the smallest one is greater than or equal to\(\sqrt i\)prime number.
consider\(dp\)Transfer. set up\(p_i\)Indicates the\(i\)Small prime numbers include:
Obviously, when creating an array, the second dimension can be rolled off, and the correctness of the transfer equation can be understood in combination with the EGYME sieve process.
It is easy to find that we only need to maintain the first dimension\(\lfloor\frac nx\rfloor\)The position is just for all the prime numbers used,\(\le\sqrt n\), so included in the former case. Simple after discretization\(dp\)Just do it.
Time complexity analysis is a bit difficult to predict, it looks like this:
Step 2:\(s(n)=\sum\limits_{i\le n}f(i)\)
It is easy to think of taking into account the contributions of prime numbers and composite numbers separately. There are two ways to think at this time:
The first type
set up\(S(i,j)=\sum\limits_{k\in([p_j,i]\cap P_j)}f(k)\), there are:
The advantage of this formula is that it is direct recursion, and it can be done without even memory\(AC\)。
Time complexity is\(n\le 10^{13}\)Time is\(O(\dfrac{n^{\frac 34}}{\log n})\), in a broader context, probably\(O(n^{1-\epsilon})\)of which\(\epsilon\)It is an infinitesimal amount.
The second type
set up\(S(i,j)=\sum\limits_{k\in([1,i]\cap P_j)}f(k)\), there are:
Simplify again:
Just recurrence, time complexity\(O(\dfrac{n^{\frac 34}}{\log n})\), but large constants. But the good news is that we can find all\(\lfloor\dfrac ni\rfloor\)。
//First Luogu template question code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,p=1e9+7,is=(p+1)/6;
namespace min25{
int n,cnt,id1[N],id2[N],v[N];
int m,pr[N],vs[N],g1[N],g2[N];
int gt(int x){return x<N?id1[x]:id2[n/x];}
int s1(int x){return x*(x+1)/2%p;}
int s2(int x){return x*(x+1)%p*(x+x+1)%p*is%p;}
int f(int x){return x%=p,(x*x-x)%p;}
void init(){
for(int i=2;i<=sqrt(n)+1;i++){
if(vs[i]) continue;pr[++cnt]=i;
for(int j=i*2;j<=sqrt(n)+1;j+=i) vs[j]=1;
}for(int l=1,r;l<=n;l=r+1){
r=n/(n/l),v[++m]=n/l;
n/l<N?id1[n/l]=m:id2[r]=m;
g1[m]=(s1(n/l%p)-1)%p;
g2[m]=(s2(n/l%p)-1)%p;
}for(int j=1;j<=cnt;j++)
for(int i=1;i<=m&&pr[j]*pr[j]<=v[i];i++){
g1[i]=(g1[i]-pr[j]*(g1[gt(v[i]/pr[j])]-g1[gt(pr[j-1])]))%p;
g2[i]=(g2[i]-pr[j]*pr[j]%p*(g2[gt(v[i]/pr[j])]-g2[gt(pr[j-1] )]) %p;
}
}int S(int x,int y){
if(pr[y]>=x) return 0;
int re=(g2[gt(x)]-g1[gt(x)]-g2[gt(pr[y])]+g1[gt(pr[y])])%p;
for(int i=y+1,w=pr[i];i<=cnt&&w*w<=x;w=pr[++i])
for(int j=1;w<=x/pr[i];j++,w*=pr[i])
re=(re+f(w)*S(x/w,i)%p+f(w*pr[i]))%p;
return re;
}int ans(int x){return init(),(S(x,0)+p+1)%p;}
} using namespace min25;
signed main(){
ios::sync_with_stdio(0);
(0),(0);
cin>>n,cout<<ans(n);
return 0;
}//second Simple function version 10^13
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e7+5,p=1e9+7;
ll n,v[N];int m,sum[N],g[N],g1[N],g2[N];
int cnt,pr[N],vs[N],id1[N],id2[N],s[N];
int gt(ll x){return x<N?id1[x]:id2[n/x];}
int md(int x){return (x>=p)?x-p:(x<0)?x+p:x;}
int md(ll x){return x-x/p*p;}
void init(){
for(int i=2;i<=sqrt(n)+1;++i){
if(vs[i]) continue;
pr[++cnt]=i,sum[cnt]=md(sum[cnt-1]+i);
for(int j=i*2;j<=sqrt(n)+1;j+=i) vs[j]=1;
}for(ll l=1,r,k;l<=n;l=r+1){
v[++m]=n/l,r=n/v[m];
v[m]<N?id1[v[m]]=m:id2[r]=m;
g1[m]=(k=md(v[m]))-1;
g2[m]=md(k*(k+1)/2-1);
}for(int j=1,c=pr[j];j<=cnt;c=pr[++j])
for(int i=1;i<=m&&c<=v[i]/c;++i){
g1[i]=md(g1[i]-g1[gt(v[i]/c)]+j-1);
g2[i]=md((ll)g2[i]-(ll)c*(g2[gt(v[i]/c)]-sum[j-1]));
}
for(int i=1;i<=m;i++) s[i]=g[i]=md(g2[i]-g1[i]);
for(int j=cnt,c=pr[j];j;c=pr[--j])
for(int i=1;i<=m&&c<=v[i]/c;++i)
for(ll k=1,w=c;w<=v[i]/c;++k,w*=c)
s[i]=md((c^k)*(s[gt(v[i]/w)]-g[gt(c)])+(ll)s[i]+(ll)(c^ (k+1));
}int ans(){
int re=0;s[m]-=2;
for(int i=1;i<=m;++i) s[i]=md(s[i]+p+3);
sort(s+1,s+m+1),m=unique(s+1,s+m+1)-s-1;
for(int i=1;i<=m;++i) re^=s[i];
return re;
}signed main(){
ios::sync_with_stdio(0);
(0),(0);
cin>>n,init(),cout<<ans();
return 0;
}