2019银川icpc F 数论分块，技巧

92 阅读 0 评论 61 点赞

我是靠谱客的博主激昂牛排，这篇文章主要介绍2019银川icpc F 数论分块，技巧，现在分享给大家，希望可以做个参考。

题意：

给出 $n$ ，计算
$sum_{a=2}^{n}(asum_{b=a}^{n}lfloor f_{a}^{-1}(b)rfloorlceil f_{b}^{-1}(a)rceil),f_{a}(x)=a^{x}$
原题如此说明 $f_{a}^{-1}(x)$ ： $f_{a}^{-1}(x)$ is the inverse function of $f_{a}(x)$

Solution：

首先需要注意一个点， $f_{a}^{-1}(x)$ 是 $f_{a}(x)$ 的反函数，而不是逆元，逆元是inverse element，反函数是inverse function

$f_{a}(b)=a^{b}$ 是个指数函数，于是反函数为对数函数 $f_{a}^{-1}(b)=log_{a}b$

于是原式即计算
$sum_{a=2}^{n}(asum_{b=a}^{n}lfloor log_{a}b rfloorlceil log_{b}arceil)$
显然题意已经包含 $a \leq b$ ，于是 $log_{b}arceil=1$ ，那么只需要计算
$sum_{a=2}^{n}(asum_{b=a}^{n}lfloor log_{a}b rfloor)$

有关对数，今天学到一个技巧，以 $n$ 为界分块处理，这样有什么好处？

当 $a > n$ 时，枚举的 $b$ 不超过 $n$ ，那么就意味 $log_{a}b rfloor=1$

于是我们先计算 $a > n$ 部分，即
$sum_{a=sqrt{n}+1}^{n}(asum_{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$
第一部分等差数列求和即可，第二部分利用以下公式求和
$sum_{i=1}^{n}i^2=frac{n(n+1)(2n+1)}{6}$
这个部分是 $O (1)$ 得到的，接着计算 $a \leq n$ 的部分：
$sum_{a=2}^{n}(asum_{b=a}^{n}lfloor log_{a}b rfloor)$
此时 $nleq10^6$ ，我们考虑枚举 $a$ ，此时如何快速求得每个 $a$ 的值，由于出现了下取整，我们可以考虑能否进行像整除分块般的操作，一部分一部分的处理，对于对数函数 $log_{a}x$ ，不难发现有这么几个区间段中，他们向下取整的值是一样的
$a,a^2-1]\ [a^2,a^3-1]\ ....\ [a^k,a^{k+1}-1]$
于是我们考虑这样子对 $b$ 的所有取值分类然后分类计算，显然最多拥有 $32$ 次幂，于是对每个 $a$ ，计算的次数都会在 $32$ 以内，是可以接受的，这部分的复杂度为 $O (n l o g n)$ ，总复杂度为 $O (n l o g n)$

需要注意分段的时候最后一段的可能不是完整的 $a^k,a^{k+1}-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
52
53
54
55
56
57
58
59
#ifndef stdjudge
#include<bits/stdc++.h>
#endif
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<numeric>
#include<ctime>
#include<cmath>
#include<vector>
#include<bitset>
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 stdjudge
freopen("in.txt","r",stdin);
#endif
cin>>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<<qm(ans+qm(n+1)*qm(limit+n+1)%mod*qm(n-limit)%mod*inv(2)%mod-qm(f(n)-f(limit)))<<'n';
return 0;
}