自动搬运

查看原文

来自洛谷，原作者为

	gesong1234 花有重开日，人有重开时||RP+=INF

搬运于2025-08-24 23:02:11，当前版本为作者最后更新于2024-08-18 11:00:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门：P10886 【MX-S3-T2】「FeOI Round 1」Journey。

思路

记 $f_i$ 表示 $i$ 的因数个数，可以用线性筛求出。

可以枚举 $g_i$ 将题目转化成式子有多少个被计算到。

我们发现如果 $a,b,c$ 能被计算到，当且仅当 $a\le i,b> i,c|(i-a)$，分情况讨论：

1. 当 $a<i$ 时，枚举 $a$ 求 $f_{i-a}$ 的和并将其记为 $sum$，那最后的贡献即为 $sum\times (n+1-i)$，但是现在求 $sum$ 是 $O(n)$ 的，因此需要使用前缀和优化。
2. 当 $a=i$ 时，$c$ 可以任取，$b$ 只要 $\ge i$ 即可，这部分的贡献为 $n\times (n+1-i)$。

综上，每一个 $g_i$ 的贡献就是 $g_i(sum\times (n+1-i)+n\times (n+1-i))$。

记得取模。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e7+10,mod=1e9+7;
int n,vis[N],pr[N],m,t,a[N],f[N],b[N];
inline void get(int n){
	f[1]=1;
	for (int i=2;i<=n;i++){
		if (!vis[i]) pr[++m]=i,a[i]=1,f[i]=2;
		for (int j=1;i*pr[j]<=n;j++){
			int x=i*pr[j];
			vis[x]=1;
			if (i%pr[j]==0){
				a[x]=a[i]+1,f[x]=f[i]/a[x]*(a[x]+1);
				break;
			} 
			else a[x]=1,f[x]=f[i]*2;
		}
	}
	for (int i=1;i<=n;i++) f[i]+=f[i-1];
}
inline int read(){
	char c=getchar();int f=1;int ans=0;
	while(c<48||c>57) (c==45?f=-1:1),c=getchar();
	while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();
	return ans*f;
}
main(){
	int n=read(),A=read(),B=read(),C=read();b[n]=read();
	get(n);
	for (int i=n-1;i>0;i--)
		b[i]=(1ll*A*b[i+1]%mod*b[i+1]%mod+1ll*B*b[i+1]%mod+C)%mod;
	int ans=0;
	for (int i=1;i<=n;i++){
		int sum=0;
	//	for (int j=1;j<i;j++) sum=(sum+f[i-j])%mod;
		sum=f[i-1];
		ans=(1ll*b[i]*(n+1-i)%mod*sum%mod+ans+1ll*b[i]*n%mod*(n+1-i)%mod)%mod;
	}
	cout <<ans;
	return 0;
}