hdu 2019 Multi-University Training Contest 2 Function

题目:

求.(n<=1e21)

解题思路:

推出式子之后就可以分块求解.式子推法可以参考公式推导

总结:

中间用到了这么一个公式.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template <class T>
void read(T &x) {
    static char ch;static bool neg;
    for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
    for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
    x=neg?-x:x;
}

const int N=1e7+5;
const int mod=998244353;
int p[N],tot;
int phi[N];
bool v[N];
void moblus(){
    phi[1]=1;tot=0;
    for(int i=2;i<N;i++){
        if(!v[i])p[tot++]=i,phi[i]=i-1;
        for(int j=0;i*p[j]<N&&j<tot;j++){
            v[i*p[j]]=1;
            if(i%p[j])phi[i*p[j]]=phi[i]*phi[p[j]];
            else{
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }
        }
    }
}
ll calc(int n,__int128 L,__int128 R){
    ll res=0;
    for(int i=1;i*i<=n;i++){
        if(n%i==0){
            res+=(R/i-L/i)%mod*phi[i]%mod;
            res%=mod;
            if(i*i!=n){
                int j=n/i;
                res+=(R/j-L/j)%mod*phi[j]%mod;
                res%=mod;
            }
        }
    }
    return res;
}
inline ll sum(ll x){
    return x*(x+1)/2%mod;
}
inline ll sum2(ll x){
    return x*(x+1)%(6ll*mod)*(2*x+1)/6%mod;
}

inline int add(int a,int b){
    return (a+=b)>=mod?a-mod:a;
}
int main(){
    int T;
    moblus();
    scanf("%d",&T);
    for(;T--;){
        __int128 n;
        read(n);
        __int128 r=1;
        for(;(r+1)*(r+1)*(r+1)-1<=n;r++);
        ll ans=calc(r,r*r*r-1,n);
        r--;
        for(int i=1;i<=r;i++){
            int j=r/i;
            ans=add(ans,1ll*add(sum2(j)*i*3%mod,add(sum(j)*3%mod,j))*phi[i]%mod);
        }
        printf("%lld\n",ans);
    }
}