题解 T121450 [Cnoi2020]明天后的幻想乡

题目传送门

好的阅读体验

题意

求 \(\{1,2,3, \cdots ,n\}\) 中长度 $l \geq 3 $ 的等比子序列个数,\(n \leq 10^{12}\) 。

分析

首先一个数列如果是等比数列,显然它的首末项都比较有限。

具体分析,设一个不能再扩展(即极长)的等比数列有 \(m+1\) 项 \(a_0,a_1, \cdots ,a_m\) ,公比 \(q=\frac{a}{b}\) ( \(a>b\) 且 \((a,b)=1\) )。那么:

\(a_m=a_1 \dfrac{a^m}{b^m}\) , \(a_0=a_n \dfrac{b^m}{a^m}\)

又由于 \(a\) 与 \(b\) 互质,可以得到 \(b^m \mid a_m\) , \(a^m \mid a_0\) 。

又 \(m \geq 3\) ,可以发现这样的 \(a_1\) 或者 \(a_n\) 的个数是 \(\sqrt{n}\) 级别的,可以考虑暴力枚举,然后 \(O(1)\) 计算出每种情况的个数。

现在问题来了,是按首项枚举还是末项呢?

如果我们确定了首项与公比,就无法快速计算在何时 $a_i \geq n $ 。但如果确定末项与公比,贡献就一定是 \(m-1\) ,因为一定有 \(a_0 \geq 0\) 。

设 \(a_0=ka^m\) , \(a_m=kb^m\) , \(a_i=ka^{m-i}b^i\) 。为避免计重,要求得到的等比数列不能再向左拓展,即 \(\forall y \in [1,a_0-1], \ y \dfrac{a}{b} \neq a_0\) 。其等价于 \(b \nmid k\) 。

有了这些以后,就可以推柿子了。

\(\sum\limits_b\sum\limits_{m+1}\sum\limits_k\sum\limits_a(m-1)\)

\(=\sum\limits_b\sum\limits_{m+1}\sum\limits_k\varphi(b)(m-1)\)

\(=\sum\limits_b\sum\limits_{m+1=3}^n(\lfloor\dfrac{n}{b^m}\rfloor-\lfloor\dfrac{n}{b^{m+1}}\rfloor)\varphi(b)(m-1)\)

\(=\sum\limits_{b=1}^{\sqrt{n}}\sum\limits_{m=2}^{n-1}(\lfloor\dfrac{n}{b^m}\rfloor-\lfloor\dfrac{n}{b^{m+1}}\rfloor)\varphi(b)(m-1)\)

线性筛出 \(\sqrt{n}\) 内的 \(\varphi(i)\) ,枚举 \(b\) 和 \(m\) 即可,时间复杂度 \(O(\sqrt{n})\) 。

代码

#include<bits/stdc++.h>
using namespace std;
const long long N=1e6+5,mod=998244353;
long long n;
long long phi[N],prime[N];
bool pd[N];
long long ans,cnt;
void init(){
	phi[1]=1;
	for(long long i=2;i<=N;i++){
		if(!pd[i]) prime[++cnt]=i,phi[i]=i-1;
		for(long long j=1;j<=cnt && i*prime[j]<=N;j++){
			pd[i*prime[j]]=1;
			if(i%prime[j]) phi[i*prime[j]]=phi[i]*(prime[j]-1);
			else{
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
		}
	}
}
int main(){
	init();
	cin>>n;
	for(long long b=2;b<=sqrt(n);b++){
		for(long long m=2;pow(b,m)<=n;m++){
			long long tmp=pow(m,x);
			ans=(ans+(n/tmp-n/tmp/m)*(phi[b])*(m-1))%mod;
		}
	}
	cout<<ans;
}
上一篇:快/光速幂学习笔记


下一篇:Pyqt-线程