简述
从某种意义上来说，莫比乌斯反演可以看作是在数论函数上的容斥。当然，它有多种形式，要视具体情况分析。
由于其与狄利克雷卷积息息相关，因此我把它们放在一块写。
前置知识
取整函数的性质
常见的数论函数
关于取值个数的问题（用于证明数论分块的时间复杂度）
[forall nin N_+,|{lfloor frac{n}{d}
floor|din N_+}|le 2sqrt{n}
]
证明
若(dlesqrt{n})，则能得到总共不超过(sqrt{n})种结果（(d)只有(sqrt{n})种选择）；
若(d>sqrt{n})，则因为(lfloor frac{n}{d}
floorlefrac{n}{d}lesqrt{n})，且(lfloor frac{n}{d}
floor)为整数，所以也最多不超过(sqrt{n})种取值；
综上所述，总共不超过(2sqrt{n})种可能取值。
( ext{Dirichlet})卷积
定义
定义两个数论函数(f,g)的( ext{Dirichlet})卷积为：
[(f*g)(n)=sum_{d|n}f(d)g(frac{n}{d})
]
性质
- ( ext{Dirichlet})卷积满足交换律和结合律。
- (epsilon)为( ext{Dirichlet})卷积的单位元，任何数论函数卷上单位元都为其本身。这很容易说明，因为当且仅当(d=n)时(epsilon(frac{n}{d})=1)，其余情况都为0，不被计入。
3 . 若(f,g)均为积性函数，则(h=f*g)也为积性函数。
简证：
[click]
设(n,m)互质：
[egin{align*}
h(n)h(m)&=sum_{d|n}f(d)g(frac{n}{d})sum_{k|m}f(k)g(frac{m}{k})\
&=sum_{d|n}sum_{k|m}f(d)f(k)g(frac{n}{d})g(frac{m}{k})\
&=sum_{d|n}sum_{k|m}f(dk)g(frac{nm}{dk})\
&=sum_{d'|nm}f(d')g(frac{nm}{d'})\
&=h(nm)
end{align*}]
由于(n,m)互质，其因数也互质，所以所有因数的组合不重不漏地构成了(nm)的因数集合。
常见形式
[egin{align*}
epsilon& =mu *1\
operatorname{d}& =1*1\
sigma& =operatorname{id}*1\
operatorname{id}& =varphi*1\
varphi& =mu*operatorname{id}\
end{align*}]
简证
[click]
[n
eq 1,n=p_1^{a_1}p_2^{a_2}cdots p_k^{a_k},k>0\
egin{align*}sum_{d|n}mu(d)&=sum_{i=0}^ksum_{j=0}^i(-1)^j inom{k}{i}\
&=sum_{i=0}^k(1-1)^j=0end{align*}]
由于(varphi)是积性函数，只需证明(k=1)的时候(operatorname{id}=varphi*1)成立即可。设此时(n=p^a)。
[egin{align*}
sum_{d|n}varphi(d)&=sum_{i=0}^a (p^i-i)\
&=sum_{i=0}^a varphi(p^i)\
&=1+sum_{i=1}^{a}p^{i-1}(p-1)\
&=1+(p-1)frac{p^a-1}{p-1}\
&=p^a\
end{align*}]
由于当(n,m)互质时，其因数除了1无交集，有：
[egin{align*}
nm&=sum_{d|n}varphi(d)sum_{k|m}varphi(k)\
&=sum_{d|n}sum_{k|m}varphi(d)varphi(k)\
&=sum_{d|n}sum_{k|m}varphi(dk)\
&=sum_{d|nm}varphi(d)
end{align*}]
则对于一般情况而言，将(n)按照质因数分解相乘即可证明(operatorname{id}=varphi*1)。
两边同时卷上(mu)即可得到:
[egin{align*}
varphi*1*mu&=operatorname{id}*mu\
Leftrightarrow varphi*epsilon&=operatorname{id}*mu\
Leftrightarrow varphi&=operatorname{id}*mu
end{align*}]
(n=1)时，正确性显然。
( ext{Möbius})反演
公式
[egin{align*}
f(n)&=sum_{d|n}g(d)\
Leftrightarrow g(n)&=sum_{d|n}mu(d)f(frac{n}{d})\
end{align*}]
证明
(1)直接代入
[egin{align*}
sum_{d|n}mu(d)f(frac{n}{d})&=sum_{d|n}mu(d)sum_{k|frac{n}{d}}g(k)\
&=sum_{k|n}g(k)sum_{d|frac{n}{k}}mu(d)\
&=sum_{k|n}g(k)epsilon(frac{n}{k})\
&=g(n)
end{align*}]
(2)进行卷积
[egin{align*}
f*mu=g*1*mu=g*epsilon=g
end{align*}]
相关练习
[HAOI2011]Problem b
题解
[click]
直接从区间考虑不方便，不妨直接考虑做前缀和和做差，再进行一个容斥。
[egin{align*}
sum_{i=1}^nsum_{j=1}^m[gcd(i,j)=k]&=sum_{i=1}^{lfloorfrac{n}{k}
floor}sum_{j=1}^{lfloorfrac{m}{k}
floor}[gcd(i,j)=1]\
&=sum_{i=1}^{lfloorfrac{n}{k}
floor}sum_{j=1}^{lfloorfrac{m}{k}
floor}epsilon(gcd(i,j))\
&=sum_{i=1}^{lfloorfrac{n}{k}
floor}sum_{j=1}^{lfloorfrac{m}{k}
floor}sum_{d|gcd(i,j)}mu(d)\
&=sum_{i=1}^{lfloorfrac{n}{k}
floor}sum_{j=1}^{lfloorfrac{m}{k}
floor}sum_{d|i,d|j}mu(d)\
&=sum_{d=1}^{min(lfloorfrac{n}{k}
floor, lfloorfrac{m}{k}
floor)}mu(d)lfloorfrac{n}{kd}
floor lfloorfrac{m}{kd}
floor\
end{align*}]
这时候前面证的性质就要派上用场了。由于(lfloorfrac{n}{x}
floor)的取值一定是连续的，我们可以将相同的值合并到同一块中计数。从前面取整函数的性质可知，使得(lfloorfrac{n}{x}
floor=lfloorfrac{n}{y}
floor)的最大(x=lfloorfrac{n}{lfloorfrac{n}{y}
floor}
floor)。这样就可以根据取值的不同来分块，利用前缀和相减再乘上一个相同的系数来计数。
又由前面所证明的，(lfloorfrac{n}{d}
floor)的取值不超过(2sqrt{n})个，所以一次计数的时间复杂度为(O(sqrt{n}))。
这就是数论分块。
至于容斥，很简单啦，理解成二维前缀和或其它方法都可以。
代码
[click]
#include <cstdio>
#include <cctype>
const int maxn=5e4+10;
int s[maxn],mu[maxn],prim[maxn];
int tot;
bool vis[maxn];
void swap(int &x,int &y) {x^=y^=x^=y;}
int min(int x,int y) {return x<y?x:y;}
int read()
{
int res=0;
char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch))
res=res*10+ch-'0',ch=getchar();
return res;
}
void prework(int n)
{
vis[0]=vis[1]=1;
mu[1]=s[1]=1;
for (int i=2;i<=n;i++)
{
if (!vis[i])
prim[++tot]=i,mu[i]=-1;
s[i]=s[i-1]+mu[i];
for (int j=1;j<=tot&&i*prim[j]<=n;j++)
{
vis[i*prim[j]]=1;
if (i%prim[j]==0)
{
mu[i*prim[j]]=0;
break;
}
mu[i*prim[j]]=-mu[i];
}
}
}
int solve(int n,int m)
{
if (n>m)
swap(n, m);
int res=0;
for (int l=1,r=1;l<=n;l=r+1)
{
r=min(n/(n/l), m/(m/l));
res+=(s[r]-s[l-1])*(n/l)*(m/l);
}
return res;
}
int main()
{
int n=read();
prework(5e4);
for (int i=1;i<=n;i++)
{
int a=read(),b=read(),c=read(),d=read(),k=read();
printf("%d
",solve(b/k, d/k)-solve((a-1)/k, d/k)-solve((c-1)/k, b/k)+solve((a-1)/k, (c-1)/k));
}
return 0;
}
[国家集训队]Crash的数字表格
题解
[click]
[egin{align*}
sum_{i=1}^nsum_{j=1}^m operatorname{lcm}(i, j)&=sum_{i=1}^nsum_{j=1}^m frac{ij}{gcd(i,j)}\
&=sum_{d=1}^{min(n,m)}frac{1}{d}sum_{i=1}^nsum_{j=1}^m ij[gcd(i,j)]=d]\
&=sum_{d=1}^{min(n,m)}frac{1}{d}sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{m}{d}
floor} (i imes d)(j imes d)[gcd(i,j)]=1]\
&=sum_{d=1}^{min(n,m)}dsum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{m}{d}
floor} ij[gcd(i,j)]=1]\
&=sum_{d=1}^{min(n,m)}dsum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{m}{d}
floor}ijsum_{k|gcd(i,j)}mu(k)\
&=sum_{d=1}^{min(n,m)}dsum_{k=1}^{min(lfloorfrac{n}{d}
floor, lfloorfrac{m}{d}
floor)}mu(k)sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{m}{d}
floor}ij[k|gcd(i,j)]\
&=sum_{d=1}^{min(n,m)}dsum_{k=1}^{min(lfloorfrac{n}{d}
floor, lfloorfrac{m}{d}
floor)}mu(k)sum_{i=1}^{lfloorfrac{n}{kd}
floor}sum_{j=1}^{lfloorfrac{m}{kd}
floor}(i imes k)(j imes k)\
&=sum_{d=1}^{min(n,m)}dsum_{k=1}^{min(lfloorfrac{n}{d}
floor, lfloorfrac{m}{d}
floor)}k^2mu(k)sum_{i=1}^{lfloorfrac{n}{kd}
floor}sum_{j=1}^{lfloorfrac{m}{kd}
floor}ij\
&=sum_{d=1}^{min(n,m)}dsum_{k=1}^{min(lfloorfrac{n}{d}
floor, lfloorfrac{m}{d}
floor)}k^2mu(k)(sum_{i=1}^{lfloorfrac{n}{kd}
floor}i)(sum_{j=1}^{lfloorfrac{m}{kd}
floor}j)\
end{align*}]
只需要预处理一下(sum_{i=1}^n i)和(sum_{i=1}^ni^2mu(i))，再进行数论分块，本题就得到了解决。
代码
[click]
#include <cstdio>
#include <cctype>
typedef long long ll;
const int maxn=1e7+10;
const int p=20101009;
int mu[maxn],prim[maxn],s[maxn],t[maxn];
int tot;
bool vis[maxn];
void swap(int &x,int &y) {x^=y^=x^=y;}
int min(int x,int y) {return x<y?x:y;}
int read()
{
int res=0;
char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch))
res=res*10+ch-'0',ch=getchar();
return res;
}
void prework(int n)
{
vis[0]=vis[1]=1;
mu[1]=s[1]=1;
for (int i=2;i<=n;i++)
{
if (!vis[i])
prim[++tot]=i,mu[i]=-1;
s[i]=s[i-1]+(ll)i*i*mu[i]%p;
if (s[i]>=p)
s[i]-=p;
else if (s[i]<0)
s[i]+=p;
for (int j=1;j<=tot&&i*prim[j]<=n;j++)
{
vis[i*prim[j]]=1;
if (i%prim[j]==0)
{
mu[i*prim[j]]=0;
break;
}
mu[i*prim[j]]=-mu[i];
}
}
for (int i=1;i<=n;i++)
{
t[i]=t[i-1]+i;
if (t[i]>=p)
t[i]-=p;
else if (t[i]<0)
t[i]+=p;
}
}
int main()
{
int n=read(),m=read();
if (n>m)
swap(n, m);
prework(m);
int ans=0;
for (int d=1;d<=n;d++)
{
int sum=0;
for (int l=1,r=1;l<=n/d;l=r+1)
{
r=min(n/d/(n/d/l), m/d/(m/d/l));
sum+=(ll)(s[r]-s[l-1])*t[n/l/d]%p*t[m/l/d]%p;
if (sum>=p)
sum-=p;
else if (sum<0)
sum+=p;
}
ans+=(ll)sum*d%p;
if (ans>=p)
ans-=p;
else if (ans<0)
ans+=p;
}
printf("%d
",ans);
return 0;
}
[SDOI2015]约数个数和
题解
[click]
首先，(operatorname{d}(ij))当然不可能用(operatorname{d}=1*1)来求。转换思路，(ij)的因数相当于是由(i)因数集合中的元素以及(j)因数集合中的元素相乘而得到的，为了使计数不重不漏，应限制相乘的两个元素互质。
因此得到了(operatorname{d}(ij)=sum_{x|i}sum_{y|j}[gcd(x,y)=1])，有个经常见到的东西就出现了。
代入式子：
[egin{align*}
sum_{i=1}^nsum_{j=1}^moperatorname{d}(ij)&=sum_{i=1}^nsum_{j=1}^msum_{x|i}sum_{y|j}[gcd(x,y)=1]\
&=sum_{i=1}^nsum_{j=1}^msum_{x|i}sum_{y|j}sum_{k|gcd(x,y)}mu(k)\
&=sum_{k=1}^{min(n,m)}mu(k)sum_{i=1}^nsum_{j=1}^msum_{x|i}sum_{y|j}[k|gcd(x,y)]\
&=sum_{k=1}^{min(n,m)}mu(k)sum_{x=1}^nsum_{y=1}^m[k|gcd(x,y)]lfloorfrac{n}{x}
floorlfloorfrac{m}{y}
floor\
&=sum_{k=1}^{min(n,m)}mu(k)sum_{x=1}^{lfloorfrac{n}{k}
floor}sum_{y=1}^{lfloorfrac{m}{k}
floor}lfloorfrac{n}{kx}
floorlfloorfrac{m}{ky}
floor\
&=sum_{k=1}^{min(n,m)}mu(k)(sum_{x=1}^{lfloorfrac{n}{k}
floor}lfloorfrac{n}{kx}
floor)(sum_{y=1}^{lfloorfrac{m}{k}
floor}lfloorfrac{m}{ky}
floor)\
end{align*}]
代码
[click]
#include <cstdio>
#include <cctype>
typedef long long ll;
const int maxn=5e4+10;
int mu[maxn],prim[maxn];
int tot;
ll s[maxn],t[maxn];
bool vis[maxn];
void swap(int &x,int &y) {x^=y^=x^=y;}
int min(int x,int y) {return x<y?x:y;}
int read()
{
int res=0;
char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch))
res=res*10+ch-'0',ch=getchar();
return res;
}
void prework(int n)
{
vis[0]=vis[1]=1;
mu[1]=s[1]=1;
for (int i=2;i<=n;i++)
{
if (!vis[i])
prim[++tot]=i,mu[i]=-1;
s[i]=s[i-1]+mu[i];
for (int j=1;j<=tot&&(ll)i*prim[j]<=n;j++)
{
vis[i*prim[j]]=1;
if (i%prim[j]==0)
{
mu[i*prim[j]]=0;
break;
}
mu[i*prim[j]]=-mu[i];
}
}
for (int i=1;i<=n;i++)
for (int l=1,r=1;l<=i;l=r+1)
{
r=i/(i/l);
t[i]+=(ll)(r-l+1)*(i/l);
}
}
int main()
{
int T=read();
prework(50000);
while(T--)
{
int n=read(),m=read();
if (n>m)
swap(n, m);
ll ans=0;
for (int l=1,r=1;l<=n;l=r+1)
{
r=min(n/(n/l), m/(m/l));
ans+=(s[r]-s[l-1])*t[n/l]*t[m/l];
}
printf("%lld
",ans);
}
return 0;
}
luogu3768 简单的数学题
本题前置知识：杜教筛
题解
[click]
先讲一个稍微麻烦一点的。（不管麻不麻烦最后都是用杜教筛的，你看看这数据范围哪是线性筛能跑得动的）
[egin{align*}
sum_{i=1}^nsum_{j=1}^m ijgcd(i,j)&=sum_{d=1}^nsum_{i=1}^nsum_{j=1}^n ij[gcd(i,j)=d]\
&=sum_{d=1}^n dsum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{n}{d}
floor}(i imes d)(j imes d)[gcd(i,j)=1]\
&=sum_{d=1}^n d^3sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{n}{d}
floor}ij[gcd(i,j)=1]\
&=sum_{d=1}^n d^3sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{n}{d}
floor}ijsum_{k|gcd(i,j)}mu(k)\
&=sum_{d=1}^n d^3sum_{k=1}^{lfloorfrac{n}{d}
floor}mu(k)sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{n}{d}
floor}ij[k|gcd(i,j)]\
&=sum_{d=1}^n d^3sum_{k=1}^{lfloorfrac{n}{d}
floor}mu(k)sum_{i=1}^{lfloorfrac{n}{kd}
floor}sum_{j=1}^{lfloorfrac{n}{kd}
floor}(i imes k)(j imes k)\
&=sum_{d=1}^n d^3sum_{k=1}^{lfloorfrac{n}{d}
floor}k^2mu(k)sum_{i=1}^{lfloorfrac{n}{kd}
floor}sum_{j=1}^{lfloorfrac{n}{kd}
floor}ij\
&=sum_{d=1}^n d^3sum_{k=1}^{lfloorfrac{n}{d}
floor}k^2mu(k)(sum_{i=1}^{lfloorfrac{n}{kd}
floor}i)^2\
end{align*}]
到这一步你会发现这跟之前有道题非常相似，但是那个数据范围(O(nsqrt{n}))能过而本题不行。所以还要进行下一步转化。
设(t_n=(sum_{i=1}^{n}i)^2=frac{(1+n)^2 n^2}{4})。
[egin{align*}
&sum_{d=1}^n d^3sum_{k=1}^{lfloorfrac{n}{d}
floor}k^2mu(k)(sum_{i=1}^{lfloorfrac{n}{kd}
floor})^2\
=&sum_{d=1}^n d^3sum_{k=1}^{lfloorfrac{n}{d}
floor}k^2mu(k)t(lfloorfrac{n}{kd}
floor)\
=&sum_{i=1}^n t(lfloorfrac{n}{i}
floor)i^2sum_{d|i}mu(d)frac{i}{d}\
=&sum_{i=1}^n t(lfloorfrac{n}{i}
floor)i^2varphi(i)\
end{align*}]
(t)很好解决，但是(i^2varphi(i))不数论分块这日子就过不下去了。下面就得用到杜教筛。
设(f(i)=i^2 varphi(i),s(n)=sum_{i=1}^n f(i))，(f)显然为积性函数。根据杜教筛，我们需要找到一个易于计算的(g)使得(h=f*g)也较为好算，通过(g(1)s(n)=sum_{i=1}^n h(i)-sum_{j=2}^n g(j)s(lfloorfrac{n}{j}
floor))即可数论分块求出(s)，再套回原式中进行数论分块。
观察(sum_{d|n}d^2varphi(d) g(frac{n}{d}))会觉得这个(d^2)非常的碍眼，想办法将它消成常数再卷(varphi)（我们已经知道了(operatorname{id}=varphi *1)，所以这会是一个比较自然的想法)。
不如将(g(x))设为(x^2)，恰好能使(h(n)=sum_{d|n}d^2varphi(d) g(frac{n}{d})=n^2sum_{d|n}varphi(d)=n^3)。而(n^3)的和又是可以(O(1))实现的，其表达式可以用拉格朗日插值法等方法得到，最后得到(sum_{i=1}^n h(i)=frac{(1+n)^2n^2}{4}=t(n))。数论分块时还需要用到(sum_{i=1}^n i=frac{n(n+1)(2n+1)}{6})。
于是(s(n)=t(n)-sum_{j=2}^n j^2 s(lfloorfrac{n}{j}
floor))，可以很快地递推出所有取值的(s(lfloorfrac{n}{d}
floor))。又因为(n)在这里和原式中没有变化，所以可以很方便地把(s(lfloorfrac{n}{d}
floor))代回原式中，所需要的值不多不少刚刚好。
具体实现看代码，命名方式与上述相同。
另一种呢，其实本质差不多，只不过变换的角度是从(operatorname{id}=varphi*1)出发的。
[egin{align*}
&sum_{i=1}^nsum_{j=1}^m ijgcd(i,j)\
=&sum_{i=1}^nsum_{j=1}^m ijsum_{d|gcd(i,j)}varphi(d)\
=&sum_{d=1}^nvarphi(d)sum_{i=1}^nsum_{j=1}^n ij[d|gcd(i,j)]\
=&sum_{d=1}^n d^2varphi(d)sum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{n}{d}
floor} ij\
=&sum_{d=1}^n d^2varphi(d)(sum_{i=1}^{lfloorfrac{n}{d}
floor}i)(sum_{j=1}^{lfloorfrac{n}{d}
floor}j)\
=&sum_{d=1}^n d^2varphi(d)frac{(1+lfloorfrac{n}{d}
floor)^2lfloorfrac{n}{d}
floor^2}{4}
end{align*}]
接下来要做的，你应该都知道了：想办法对(d^2varphi(d))做杜教筛。
代码就不写了，差不多的，下面放的是上一个做法的代码。
代码
[click]
#include <cstdio>
#include <cctype>
#include <cmath>
#include <map>
using std::map;
typedef long long ll;
const int maxn=1e7+10;
int prim[maxn],s[maxn];
int tot,lim,p;
int inv_4,inv_6;
ll n;
bool vis[maxn];
map<ll,int> S;
ll read()
{
ll res=0;
char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch))
res=res*10+ch-'0',ch=getchar();
return res;
}
void prework(int n)
{
vis[0]=vis[1]=1;
s[1]=1;
for (int i=2;i<=n;i++)
{
if (!vis[i])
prim[++tot]=i,s[i]=i-1;
for (int j=1;j<=tot&&(ll)i*prim[j]<=n;j++)
{
vis[i*prim[j]]=1;
if (i%prim[j]==0)
{
s[i*prim[j]]=s[i]*prim[j];
break;
}
s[i*prim[j]]=s[i]*(prim[j]-1);
}
}
for (int i=2;i<=n;i++)
s[i]=((ll)i*i%p*s[i]%p+s[i-1])%p;
}
int power(int a,int n)
{
int res=1;
while(n)
{
if (n&1)
res=(ll)res*a%p;
a=(ll)a*a%p;
n>>=1;
}
return res;
}
int getSquare(ll n) {return n%=p,n*(n+1)%p*(2*n+1)%p*inv_6%p;}
int getCubic(ll n) {return n%=p,(n+1)*(n+1)%p*n%p*n%p*inv_4%p;}
int solve(ll n)
{
if (n<=lim)
return s[n];
else
{
map<ll,int>::iterator it=S.find(n);
if (it!=S.end())
return (*it).second;
}
int res=getCubic(n);
for (ll l=2,r=1;l<=n;l=r+1)
{
r=n/(n/l);
res-=(ll)(getSquare(r)-getSquare(l-1))*solve(n/l)%p;
if (res<0)
res+=p;
else if (res>=p)
res-=p;
}
return S[n]=res;
}
int main()
{
p=read(),n=read();
lim=pow(n, 2.0/3.0);
prework(lim);
int ans=0;
inv_4=power(4, p-2),inv_6=power(6, p-2);
for (ll l=1,r=1;l<=n;l=r+1)
{
r=n/(n/l);
ans+=(ll)getCubic(n/l)*(solve(r)-solve(l-1))%p;
if (ans<0)
ans+=p;
else if (ans>=p)
ans-=p;
}
printf("%d
",ans);
return 0;
}
小结
对于一个式子，要利用狄利克雷卷积的几种常见形式及一些常用的套路（如变换求和顺序、提取公因数等）来达到简化式子进行数论分块的目的。
当数据范围显示线性的时间复杂度无法通过时，考虑杜教筛等低于线性复杂度的方法——也就是说，要善于利用数据范围这一提示信息推测正解时间复杂度。
剩下的大概就是多练习找到推式子的感觉了。
注意小心数据溢出导致的错误。