2019 acm-icpc银川站F.Function!(数学分块)

给你一个式子${\sum }_{a=2}^n\left(a{\sum }_{b=a}^n\lfloor f_a^{-1}\left(b\right)\rfloor \lceil f_b^{-1}\left(a\right)\rceil \right)$让你求值。
$f_a(b)=a^b,f_a^{-1}(b)=lo{g}_{a}b$

我们首先观察一下这个式子，显然$\because b\ge a,\therefore \lceil f_b^{-1}\left(a\right)\rceil =1$
那么化简一下这个式子就是${\sum }_{a=2}^{n}a{\sum }_{b=a}^n\lfloor lo{g}_{a}b\rfloor$，显然右边的对数函数是可以分块计算的，枚举$a$,对于每个$a$，每次枚举对数函数的答案然后跳即可。当计算到$a\ast a>n$的时候，那么整个$b=[a,n]$的对数答案显然都是1了，这个时候直接$O(1)$计算即可。
注意中间的取模细节。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
LL n;
const LL mod = 998244353;
LL pd(LL a,LL b){
LL ans=1;
while(b){
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
LL get(LL x){
x%=mod;
LL inv=pd(6,mod-2);
return x%mod*(x+1)%mod*(2*x+1)%mod*inv%mod;
}
int main() {
ios::sync_with_stdio(false);
cin>>n;
LL ans=0;
LL inv=pd(2,mod-2);
for(LL i=2;i<=n;i++){
LL res=1;
if(i*i>n){
LL q=n%mod;
ans=ans+(q+1)%mod*(i+q)%mod*(q-i%mod+1+mod)%mod*inv%mod;
ans=ans-(get(n)-get(i-1)+10ll*mod)%mod+10ll*mod;
ans%=mod;
break;
}
for(LL l=i,tmp=0;l<=n;l=res,tmp++){
res*=i;
if(res>n){
ans=ans+i%mod*tmp*(n%mod-l+1+mod)%mod;
break;
}else{
ans=ans+i%mod*tmp*(res%mod-l+mod)%mod;
}
}
}
cout<<ans<<endl;
return 0;
}

最后

以上就是多情饼干为你收集整理的2019 acm-icpc银川站F.Function!(数学分块)的全部内容，希望文章能够帮你解决2019 acm-icpc银川站F.Function!(数学分块)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。