https://nanti.jisuanke.com/t/42386
byf当时没写出来这题情有可原，我也快写了40分钟。。。留下了数学功底薄弱的泪水
观察发现f^-1_{b}_(a)始终为1
然后考虑前面的部分为1*(a^2-a)+2*(a^3-a^2)+...d*(n-a^d)，这个东西化简一下就是
d*n+d-a^d-a^(d-1)-...-a^2-a
d可以logn求，前面部分可以直接算，后面部分就是个等比数列求和
然后我们发现当a>sqrt(n)的时候，后面那个式子全是1
于是暴力枚举a=2--sqrt(n)，logn算出答案
然后后面的部分就是n*(1)+(n-1)*2....i*(n-i+1)
这个东西用一下那个(1+n)*n/2和(n)*(n+1)*(2*n+1)/6这两个式子就搞完了
总复杂度就是sqrt(n)*logn的
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxl=1e6+10; const int mod=998244353; ll n,ans; inline void prework() { scanf("%lld",&n); } inline ll qp(ll a,ll b) { ll ans=1,cnt=a; while(b) { if(b&1) ans=ans*cnt%mod; cnt=cnt*cnt%mod; b>>=1; } return ans; } inline void mainwork() { ll i,x,mi,dec,res;ans=0; for(i=2;i<=n;++i) { if(i*i>n) break; x=i;mi=1; while(x*i<=n) mi++,x*=i; ans=(ans+i*mi%mod*n%mod+i*mi%mod)%mod; dec=i*i%mod*((qp(i,mi)-1+mod)%mod)%mod; dec=dec*qp(i-1,mod-2)%mod; ans=(ans-dec+mod)%mod; } res=(__int128)(n+i)%mod*(n-i+1)%mod*qp(2,mod-2)%mod; res=(__int128)(n+1)%mod*res%mod; dec=(__int128)n%mod*((n+1)%mod)%mod*(2*n+1)%mod*qp(6,mod-2)%mod; dec=(dec-(i-1)*(i)%mod*(2*i-1)%mod*qp(6,mod-2)%mod+mod)%mod; ans=(ans+res-dec+mod)%mod; } inline void print() { printf("%lld\n",ans); } int main() { prework(); mainwork(); print(); return 0; }
