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

83 阅读 0 评论 55 点赞

我是靠谱客的博主多情饼干，这篇文章主要介绍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)=log_ab$

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#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;
}