2019银川icpc F 数论分块，技巧
题意：
给出nnn，计算
∑a=2n(a∑b=an⌊fa−1(b)⌋⌈fb−1(a)⌉),fa(x)=ax\sum_{a=2}^{n}(a\sum_{b=a}^{n}\lfloor f_{a}^{-1}(b)\rfloor\lceil f_{b}^{-1}(a)\rceil),f_{a}(x)=a^{x} a=2∑n(ab=a∑n⌊fa−1(b)⌋⌈fb−1(a)⌉),fa(x)=ax
原题如此说明fa−1(x)f_{a}^{-1}(x)fa−1(x)：fa−1(x)f_{a}^{-1}(x)fa−1(x) is the inverse function of fa(x)f_{a}(x)fa(x)
Solution：
首先需要注意一个点，fa−1(x)f_{a}^{-1}(x)fa−1(x)是fa(x)f_{a}(x)fa(x)的反函数，而不是逆元，逆元是inverse element，反函数是inverse function
fa(b)=abf_{a}(b)=a^{b}fa(b)=ab是个指数函数，于是反函数为对数函数fa−1(b)=logabf_{a}^{-1}(b)=log_{a}bfa−1(b)=logab
于是原式即计算
∑a=2n(a∑b=an⌊logab⌋⌈logba⌉)\sum_{a=2}^{n}(a\sum_{b=a}^{n}\lfloor log_{a}b \rfloor\lceil log_{b}a\rceil) a=2∑n(ab=a∑n⌊logab⌋⌈logba⌉)
显然题意已经包含a≤ba\leq ba≤b，于是⌈logba⌉=1\lceil log_{b}a\rceil=1⌈logba⌉=1，那么只需要计算
∑a=2n(a∑b=an⌊logab⌋)\sum_{a=2}^{n}(a\sum_{b=a}^{n}\lfloor log_{a}b \rfloor) a=2∑n(ab=a∑n⌊logab⌋)
有关对数，今天学到一个技巧，以n\sqrt{n}n为界分块处理，这样有什么好处？
当a>na>\sqrt{n}a>n时，枚举的bbb不超过nnn，那么就意味⌊logab⌋=1\lfloor log_{a}b \rfloor=1⌊logab⌋=1
于是我们先计算a>na>\sqrt{n}a>n部分，即
∑a=n+1n(a∑b=an1)=∑a=n+1na(n−a+1)=(n+1)∑a=n+1na−∑a=n+1na2\sum_{a=\sqrt{n}+1}^{n}(a\sum_{b=a}^{n}1)=\sum_{a=\sqrt{n}+1}^{n}a(n-a+1)=(n+1)\sum_{a=\sqrt{n}+1}^{n}a-\sum_{a=\sqrt{n}+1}^{n}a^2 a=n+1∑n(ab=a∑n1)=a=n+1∑na(n−a+1)=(n+1)a=n+1∑na−a=n+1∑na2
第一部分等差数列求和即可，第二部分利用以下公式求和
∑i=1ni2=n(n+1)(2n+1)6\sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6} i=1∑ni2=6n(n+1)(2n+1)
这个部分是O(1)O(1)O(1)得到的，接着计算a≤na\leq \sqrt{n}a≤n的部分：
∑a=2n(a∑b=an⌊logab⌋)\sum_{a=2}^{n}(a\sum_{b=a}^{n}\lfloor log_{a}b \rfloor) a=2∑n(ab=a∑n⌊logab⌋)
此时n≤106n\leq10^6n≤106，我们考虑枚举aaa，此时如何快速求得每个aaa的值，由于出现了下取整，我们可以考虑能否进行像整除分块般的操作，一部分一部分的处理，对于对数函数logaxlog_{a}xlogax，不难发现有这么几个区间段中，他们向下取整的值是一样的
[a,a2−1][a2,a3−1]....[ak,ak+1−1][a,a^2-1]\\ [a^2,a^3-1]\\ ....\\ [a^k,a^{k+1}-1] [a,a2−1][a2,a3−1]....[ak,ak+1−1]
于是我们考虑这样子对bbb的所有取值分类然后分类计算，显然最多拥有323232次幂，于是对每个aaa，计算的次数都会在323232以内，是可以接受的，这部分的复杂度为O(nlogn)O(\sqrt{n}logn)O(nlogn)，总复杂度为O(nlogn)O(\sqrt{n}logn)O(nlogn)
需要注意分段的时候最后一段的可能不是完整的[ak,ak+1−1][a^k,a^{k+1}-1][ak,ak+1−1]区间
#ifndef stdjudge
#include
#endif
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;using ll=long long;
const int N=8e5+5,inf=0x3fffffff;
const long long INF=0x3fffffffffffffff,mod=998244353;ll n;ll qm(ll x)
{return (x%mod+mod)%mod;
}ll qpow(ll a,ll b)
{ll ret=1,base=a;while(b){if(b&1) ret=ret*base%mod;base=base*base%mod;b>>=1;}return ret;
}ll inv(ll x){return qpow(x,mod-2);}ll f(ll x)
{return qm(x)*qm(x+1)%mod*qm(2*qm(x)%mod+1)%mod*inv(6)%mod;
}int main()
{#ifdef stdjudgefreopen("in.txt","r",stdin);#endifcin>>n;ll ans=0,limit=1;for(ll i=2;i*i<=n;i++){limit++;ll last=i,now=i*i,val=1;while(1){bool flag=(now-1>=n); now=min(now,n);ans=(ans+qm(i)*qm(val)%mod*qm(now-last+(flag))%mod)%mod;last=now; now*=i; val++;if(flag) break;}}cout<