数论分块 O(Tsqrt(n)) TLE on #1 求助
查看原帖
数论分块 O(Tsqrt(n)) TLE on #1 求助
305928
zhoumurui楼主2025/6/24 22:16
#include<bits/stdc++.h>
using namespace std;
int primes[4000005],st[4000005],cnt;
long ans[1000005];
void init(int k=1000000){
    ans[1]=1;
    for (int i=2;i<=k;i++){
        if (!st[i]){
            primes[++cnt]=i;
            ans[i]=i-1;
        }
        for (int j=1;primes[j]<=k/i;j++){
            st[primes[j]*i]=1;
            if (i%primes[j]==0){
                ans[primes[j]*i]=primes[j]*ans[i];
                break;
            }
            else ans[primes[j]*i]=ans[i]*(primes[j]-1);
        }
    }
    for (int i=2;i<=k;i++)ans[i]+=ans[i-1];
}
signed main(){
    int n;
    init();
    while (cin>>n){
        if (n==0)return 0;
        
        long long res=0,l=1,r;
        while (l<=n){
            r=n/(n/l);
            res+=(ans[n/l]-1)*(r+l)*(r-l+1)/2;
            l=r+1;
        }
        cout<<res<<"\n";
    }
    return 0;
}
2025/6/24 22:16
加载中...