icontofig | 发布于 2020-03-29 17:11:22 | 阅读量 82 | 数论 mobius反演 筛法 min25筛
发布于 2020-03-29 17:11:22 | 数论 mobius反演 筛法 min25筛
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
typedef long long ll;
ll g[maxn],w[maxn],id1[maxn],id2[maxn],spr[maxn],smu[maxn],pr[maxn];
int nop[maxn],mu[maxn];
const ll mod = 998244353;
int tot = 0,cnt = 0;
void euler_init(){
    nop[1] = 1;
    mu[1] = 1;
    smu[1] = 1;
    for(int i = 2;i < maxn;++i){
        if(!nop[i]){
            mu[i] = -1;
            pr[++tot] = i;
            spr[tot] = spr[tot-1] + i;
        }
        smu[i] = smu[i-1] + (mu[i] == 0 ? 0 : 1);
        for(int j = 1;j <= tot && pr[j] * i < maxn;++j){
            nop[pr[j] * i] = 1;
            if(i % pr[j] == 0){
                mu[i*pr[j]] = 0;
                break;
            }
            mu[i*pr[j]] = -mu[i];
        }
    }
    return;
}
ll A(ll n,ll p){
    if(p*p > n)return n / p;
    return n/p - A(n/p,p);
}
ll S(ll n){
    if(n < maxn)return smu[n];
    ll ans = 0;
    for(ll d = 1;d*d <= n;++d){
        if(mu[d] == 1)
            ans = (ans + n / d / d % mod) % mod;
        else if(mu[d] == -1)
            ans = (ans + mod - n / d / d % mod) % mod;
    }
    return ans;
}
ll n,sqr;
int t;
void init(){
    sqr = sqrt(n);
    cnt = 0;
    ll last = 0;
    for(ll i = 1;i <= n;i = last + 1){
        w[++cnt] = n / i;
        g[cnt] = (w[cnt] - 1 + mod) % mod * ((w[cnt]+2) % mod) % mod;
        last = n/(n/i);
        if(g[cnt] & 1)g[cnt] += mod;
        g[cnt] >>= 1;
        if(w[cnt] <= sqr)id1[w[cnt]] = cnt;
        else id2[last] = cnt;
    }
    for(ll i = 1;i <= tot;++i){
        for(int j = 1;j <= cnt && pr[i]*pr[i] <= w[j];j++){
            ll k = (w[j] / pr[i] <= sqr) ? id1[w[j]/pr[i]] : id2[n/(w[j]/pr[i])];
            g[j] = (g[j] + mod - pr[i] * ((g[k] - spr[i-1] + mod)%mod)%mod)%mod;
        }
    }
    return;
}
int main(){
    euler_init();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--){
        cin >> n;
        init();
        ll ans = 0;
        for(ll x = 1;x < cnt;++x){
            if(w[x+1] >= sqr){
                ll t = ((g[x] - g[x+1] + mod)%mod) * (n / w[x] % mod) % mod;
                t = t * ((n - n / w[x] + mod) % mod) % mod;
                ans = (ans + t) % mod;
            }
            else{
                for(int i = 1;i <= tot && pr[i] <= w[x];++i){
                    ll temp = A(n,pr[i]);
                    ans = (ans + pr[i] * (temp%mod)%mod * ((n-temp+mod)%mod)%mod)%mod;
                }
                break;
            }
        }
        ll now,pre = 0;
        for(ll i = 1,last;i <= n;i = last + 1){
            last = n/(n/i);
            ll temp = sqrt(n/i);
            temp = temp*(temp-1) / 2 % mod;
            now = S(last);
            ans = (ans + temp * ((now + mod - pre) % mod) % mod) % mod;
            pre = now;
        }
        cout << ans << "\n";
    }
    return 0;
}

 


内容更新于: 2020-03-29 17:14:01
链接地址: http://blog.leanote.com/post/icontofig/a980608c84e4

上一篇: HDU6417 Rikka with APSP min25筛+mobius反演

下一篇: SWERC 2019-20 Problem G. Swapping Places 拓扑排序

82 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航