Open sx349 opened 4 years ago
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<' '<<x<<endl
#ifndef ONLINE_JUDGE
#define pia getchar
#else
#define pia nc
#endif
char nc(){
static char buf[1<<25],*p=buf,*q=buf;
if(p==q&&(q=(p=buf)+fread(buf,1,1<<25,stdin),p==q))return EOF;
return *p++;
}
template<class T>void rd(T&x){
short f=1;x=0;
char ch=pia();
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=pia();
}while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=pia();
}x*=f;
}
template<class T>void wr(T x){
if(x<0)putchar('-'),x=-x;
if(x>=10)wr(x/10);
putchar(x%10+48);
}
#define int __int128
#define maxn 2333333
const int p=1e9;
int lpf[maxn],pri[maxn],pcnt,spri[maxn],mx;
void shai(int n){
for(int i=2;i<=n;i++){
if(!lpf[i])pri[lpf[i]=++pcnt]=i,spri[pcnt]=spri[pcnt-1]+i;
for(int j=1;j<=lpf[i]&&i*pri[j]<=n;j++)lpf[i*pri[j]]=j;
}
}
__int64 N,lim;
int ans;
int ge[maxn],le[maxn],tot;
#define id(x) ((x)<=lim?le[x]:ge[N/(x)])
int li[maxn],G[maxn][2];
void init(int n){
tot=0;
for(int i=1,j;i<=n;i=n/j+1){
j=n/i;
id(j)=++tot;
li[tot]=j;
G[tot][0]=j%p-1;
if(j&1)G[tot][1]=(j-1)/2*(j+2)%p;
else G[tot][1]=(j+2)/2*(j-1)%p;
}
}
void calcFprime(){
for(int k=1;pri[k]<=lim;k++)
for(int i=1;li[i]>=pri[k]*pri[k];i++){
int d=id(li[i]/pri[k]);
if(i==1)ans=(ans+pri[k]*(G[d][0]-(k-1)+p))%p;
G[i][0]-=G[d][0]-(k-1)-p;
G[i][1]-=pri[k]*(G[d][1]-spri[k-1])%p-p;
G[i][0]%=p,G[i][1]%=p;
}
}
signed main(){
cin>>N;
lim=sqrt(N);
shai(lim+1000);
init(N);
ans=0;
calcFprime();
ans+=G[1][1];
wr(ans%p);
}
min25筛即可,原题是https://www.luogu.com.cn/problem/SP19975
https://pe-cn.github.io/521/
Problem 521 Smallest prime factor Let smpf(n) be the smallest prime factor of n.smpf(91)=7 because 91=7×13 and smpf(45)=3 because 45=3×3×5.Let S(n) be the sum of smpf(i) for 2 ≤ i ≤ n.E.g. S(100)=125