$Min$_$25$筛模版题
为什么泥萌常数都那么小啊$ QAQ$
传送门：
题意：
$ f(1)=1$
$ f(p^c)=p⊕c（p 为质数，⊕ 表示异或）$$ f(ab)=f(a)f(b)（a 与 b 互质）$求$ \sum\limits_{i=1}^n f(i)$
$ solution:$
显然有$ f(P_i)=P_i-1+2*[P_i=2]$
暂时忽略$ P_i=2$的情况求出质数贡献
然后再把答案$ +2$即可
$ my \ code: $
#include#include #include #include #include #include #include #define p 1000000007#define M 200010#define rt register int#define ll long longusing namespace std;inline ll read(){ ll x = 0; char zf = 1; char ch = getchar(); while (ch != '-' && !isdigit(ch)) ch = getchar(); if (ch == '-') zf = -1, ch = getchar(); while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return x * zf;}void write(ll y){ if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);}void writeln(const ll y){write(y);putchar('\n');}int i,j,k,m,x,y,z,cnt,sz;ll n;int sp[M],ss[M];bool pri[M];int id1[M],id2[M],t,h[M];ll g[M],q[M];#define inv2 500000004void init(){ sz=sqrt(n); for(rt i=2;i<=sz;i++){ if(!pri[i])ss[++cnt]=i,sp[cnt]=(sp[cnt-1]+i)%p; for(rt j=1;i*ss[j]<=sz&&j<=cnt;j++){ pri[i*ss[j]]=1; if(i%ss[j]==0)break; } } for(ll i=1;i<=n;){ ll v=n/i;ll R=n/v;q[++t]=v; if(v<=sz)id1[v]=t;else id2[R]=t; v%=p;h[t]=v-1;g[t]=v*(v+1)%p*inv2%p-1; i=R+1; }}inline int id(const ll x){ return x<=sz?id1[x]:id2[n/x];}int S(ll x,int y){ if(x<=1||ss[y]>x)return 0; ll ret=g[id(x)]-sp[y-1]+y-1; for(rt i=y;(ll)ss[i]*ss[i]<=x&&i<=cnt;i++) for(ll j=ss[i],e=1;j*ss[i]<=x;j*=ss[i],e++) (ret+=(ll)(ss[i]^e)*S(x/j,i+1)+(ss[i]^e+1))%=p; return ret;}int main(){ n=read();init(); for(rt j=1;j<=cnt;j++) for(rt i=1;i<=t&&q[i]>=(ll)ss[j]*ss[j];i++){ const int k=id(q[i]/ss[j]); (g[i]-=(ll)ss[j]*(g[k]-sp[j-1]))%=p; (h[i]-=(h[k]-j+1))%=p; } for(rt i=1;i<=t;i++)(g[i]-=h[i])%=p; if(n==1)cout<<1;else cout<<(S(n,1)+3+p)%p; return 0;}