欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

bzoj3944 Sum

程序员文章站 2022-07-02 21:50:07
"题目链接" problem 给出一个$n,n include include include include include include include include using namespace std; typedef long long ll; const int N = 50001 ......

题目链接

problem

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

\[\sum\limits_{i=1}^n\varphi(i),\sum\limits_{i=1}^n\mu(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--

bzoj3944 Sum

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;
}