hdu 6588 Function【数学】

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6588
题解：(我也想自己以后比赛的时候可以手推出这样的演算啊啊啊啊。。。。。)

AC代码：（可能有些windows跑不了__int128）

#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
typedef long long ll;
const int N=1e7+5;
ll phi[N];
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;
}
int p[N];
int vis[N],prime[N];
int tot=0;
void Calphi()
{
    phi[1]=1;
    for(int i=2;i<N;i++)
    {
        if(!vis[i])
        {
            prime[tot++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<tot;j++)
        {
            if(i*prime[j]>N)
                break;
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
            {
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
            
        }
    }
}

ll sangen(__int128 n,__int128 l,__int128 r)
{
    if(n==1)
        return n;
    __int128 mid;
    ll ans;
    while (l<=r)
    {
        mid=(l+r)/2;
        if(mid*mid*mid<=n)
        {
            ans=mid;
            l=mid+1;
        }
        else
        {
            r=mid-1;
        }
        
    }
    return (ll)ans;
}
ll qpow(ll x,ll y)
{
    ll ans=1;
    while(y)
    {
        if(y&1)
            ans=ans*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return ans;
}
const __int128 maxx=1e8,minn=1;
int main()
{
    int t;
    Calphi();
    //cout<<phi[100]<<endl;
    scanf("%d",&t);
    while(t--){
        __int128 n;
        read(n);
        ll a=sangen(n,minn,maxx);
        ll r=a-1;
       // cout<<a<<" "<<r<<endl;
        ll ans=0;
        __int128 ta=(__int128)a*a*a-1;

        for(ll t=1;t*t<=a;t++)
        {
            if(a%t==0)
            {
                ll tmp1=(((n/t)-ta/t)%mod+mod)%mod;
                ans=(ans+phi[t]*(tmp1)%mod)%mod;
                if(t*t!=a)
                {
                    ll tmp=a/t;
                    ll tmp2=(((n/tmp)-ta/tmp)%mod+mod)%mod;
                    ans=(ans+phi[tmp]*tmp2%mod)%mod;
                }
            }
        }
        ll inv2=qpow(2,mod-2);
        ll inv6=qpow(6,mod-2);
        for(ll t=1;t<=r;t++)
        {
            ll tmp1=(ll)(r/t);
            ll tmp2=3*t%mod*tmp1%mod*(1+tmp1)%mod*(2LL*tmp1%mod+1)%mod*inv6%mod;
            tmp2=(tmp2+3*(1+tmp1)%mod*tmp1%mod*inv2%mod)%mod;
            tmp2=(tmp2+tmp1)%mod*phi[t]%mod;
            ans=(ans+tmp2)%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}
/*
10
64
180
526
267
775
649
749
908
300
255
*/