题目链接

problem

给出一个(n,n < 2^{31})。分别求

[sumlimits_{i=1}^nvarphi(i),sumlimits_{i=1}^nmu(i)]

solution

(varphi(i))和(mu(i))都是积性函数。

且(varphi(p^k)=(p-1)p^{k-1})，所以可以直接(min_25)筛了。

因为(varphi(p)=p-1，p是质数)，g函数不好处理

所以将(varphi(p))分为两个函数(f_1(p)=p,f_2(p)=1)。然后分别求(g)和(h)。

(mu)预处理就直接是(-h)了。

然后(min_25)筛模板就行了。

rp–

code

/* * @author: wxyww * @date:   2019-12-25 20:16:31 * @last modified time: 2019-12-25 21:38:39 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> #include<cmath> using namespace std; typedef long long ll; const int n = 500010; ll read() {     ll x = 0,f = 1;char c = getchar();     while(c < '0' || c > '9') {         if(c == '-') f = -1; c = getchar();     }     while(c >= '0' && c <= '9') {         x = x * 10 + c - '0'; c = getchar();     }     return x * f; } ll m,n,pri[n],vis[n],js,tot,g[n],h[n],sum[n]; void pre() {     for(int i = 2;i <= 500000;++i) {         if(!vis[i]) pri[++js] = i,sum[js] = sum[js - 1] + i;         for(int j = 1;j <= js && 1ll * pri[j] * i <= 500000;++j) {             vis[pri[j] * i] = 1;             if(i % pri[j] == 0) break;         }     } } ll w[n],id1[n],id2[n]; ll sphi(ll now,ll x) {     if(now <= 1 || pri[x] > now) return 0;          ll k;      if(now <= m) k = id1[now];     else k = id2[n / now];     ll ret = g[k] - h[k] - sum[x - 1] + x - 1;      for(int k = x;k <= tot && pri[k] * pri[k] <= now;++k) {         ll p = pri[k];         for(int e = 1;p * pri[k] <= now;++e,p *= pri[k]) {             ret += (pri[k] - 1) * (p / pri[k]) * sphi(now / p,k + 1) + p * (pri[k] - 1);         }     }     return ret; } ll smu(ll now,ll x) {     if(now <= 1 || pri[x] > now) return 0;      ll  k;     if(now <= m) k = id1[now];     else k = id2[n / now];      ll ret = -h[k] + x - 1;     for(int k = x;k <= tot && pri[k] * pri[k] <= now;++k) {              ret -= smu(now / pri[k],k + 1);     }      return ret; } void solve() {     m = sqrt(n);     if(!n) return (void)puts("0 0");     tot = 0;     // memset(g,0,sizeof(g));memset(h,0,sizeof(h));      for(ll l = 1,r;l <= n;l = r + 1) {         r = n / (n / l);         w[++tot] = n / l;         if(n / l <= m) id1[n / l] = tot;         else id2[r] = tot;          g[tot] = ((w[tot] + 2) * (w[tot] - 1)) / 2;         h[tot] = w[tot] - 1;      }     // puts("!!");     for(int j = 1;j <= js && pri[j] <= m;++j) {         for(int i = 1;i <= tot && 1ll * pri[j] * pri[j] <= w[i];++i) {             ll tmp = w[i] / pri[j];             int k;             if(tmp <= m) k = id1[tmp];             else k = id2[n / tmp];              g[i] -= pri[j] * (g[k] - sum[j - 1]);             h[i] -= h[k] - j + 1;         }     }      // for(int i = 1;i <= tot;++i) printf("%lld ",h[i]);     // puts("");     // puts("!");     cout<<sphi(n,1) + 1 <<" "<<smu(n,1) + 1<<endl;     // puts("!!!"); } int main() {     int t = read();          pre();      while(t--) {         n = read();solve();     }      return 0; }