P7486 「Stoi2031」彩虹题解

题解区查询怎么都是根号

\log

的？？？？

考虑取离散对数，求出模

32465177

意义下的原根

g=3

，同时把询问差分成四个前缀，问题变成求：

A=\sum_{i}\sum_{j}\text{lcm}(i,j)\log \text{lcm}(i,j)

然后

g^A

即为答案。

随便推点式子（下取整省略不写）：

\begin{aligned} &\sum_i\sum_j\text{lcm}(i,j)\log \text{lcm}(i,j)\\ =&\sum_i\sum_j\dfrac{ij}{\gcd(i,j)}(\log i+\log j-\log \gcd(i,j))\\ =&\sum_d\sum_i\sum_j[d=\gcd(i,j)]\dfrac{ij}{d}(\log i+\log j-\log d)\\ =&\sum_d\sum_{i=1}^{\frac{l}{d}}\sum_{j=1}^{\frac{r}{d}}[\gcd(i,j)=1]ijd(\log id+\log jd-\log d)\\ =&\sum_d\sum_{i=1}^{\frac{l}{d}}\sum_{j=1}^{\frac{r}{d}}\sum_{e\mid \gcd(i,j)}\mu(e)ijd(\log id+\log jd-\log d)\\ =&\sum_dd\sum_e\mu(e)e^2\sum_{i=1}^{\frac{l}{de}}\sum_{j=1}^{\frac{r}{de}}ij(\log ide+\log jde-\log d)\\ =&\sum_{T=de}T\sum_{e\mid T}\mu(e)e\sum_i\sum_jij(\log iT+\log jT-\log d) \end{aligned}

只拿

\log iT

一项的求和出来说，剩下同理。

跟

e

有关的一项可以

\mathcal O(n\ln n)

预处理成为

F(T)

：

\begin{aligned} &\sum_TTF(T)\sum_i\sum_jij\log iT\\ =&\sum_TTF(T)\sum_i\sum_jij(\log i+\log T)\\ =&\sum_TTF(T)\sum_ii(\sum_jj\log i+\sum_j j\log T)\\ =&\sum_TTF(T)(\sum_j j)(\sum_ii\log i+\log T\sum_ii)\\ \end{aligned}

然后这个式子就可以整除分块了，预处理

TF(T),i\log i,\log T

的前缀和即可。

时间复杂度

\mathcal O(mod+n\ln n+t\sqrt n)

。

第二项可以 dirichlet 前缀和做到

\mathcal O(n\log\log n)

，懒得写了。

CPP

#define mod 32465177
using mint = modint<mod-1>;
#define g 3
#define maxn 1001000
mint w[maxn];
int mu[maxn];
bool notprime[maxn];
int prime[maxn],cnt;
mint F[maxn],G[maxn],H[maxn],I[maxn],J[maxn];
void getprime(int n) {
	mu[1]=notprime[1]=1;
	for(int i=2; i<=n; ++i) {
		if(not notprime[i]) {
			prime[++cnt]=i;
			mu[i]=-1;
		}
		for(int j=1; j<=cnt&&prime[j]*i<=n; ++j) {
			notprime[i*prime[j]]=1;
			if(i%prime[j]==0) {
				mu[i*prime[j]]=0;
				break;
			}
			mu[i*prime[j]]=-mu[i];
		}
	}
	rep(i,1,n)mu[i]*=i;
	rep(i,1,n)for(int j=i; j<=n; j+=i)F[j]+=mu[i],G[j]+=w[j/i]*mu[i];
	rep(i,1,n)F[i]*=i; 
	rep(i,1,n)H[i]=H[i-1]+G[i]*i,I[i]=I[i-1]+F[i],J[i]=J[i-1]+F[i]*w[i];
}
int n;
int arr[maxn<<1],m;
int gt(int n) {
	int l=1,r;
	while(l<=n) {
		r=n/(n/l);
		arr[m++]=l;
		arr[m++]=r+1;
		l=r+1;
	}
	return m;
}
mint W[maxn],Pre[maxn];
mint calc(int l,int r) {
	mint res=0;
	m=0;
	int p=gt(l),q=gt(r);
	inplace_merge(arr,arr+p,arr+q);
	m=unique(arr,arr+m)-arr;
	rep(i,0,m-2) {
		int p=arr[i],q=arr[i+1]-1;
		int L=l/p,R=r/q;
		res-=(H[q]-H[p-1])*(1ll*L*(L+1)/2)*(1ll*R*(R+1)/2);
	}
	auto wrk=[&](int l,int r)->mint {
		mint res=0;
		m=0;
		int p=gt(l),q=gt(r);
		inplace_merge(arr,arr+p,arr+q);
		m=unique(arr,arr+m)-arr;
		rep(i,0,m-2) {
			int p=arr[i],q=arr[i+1]-1;
			int L=l/p,R=r/q;
			res+=(mint)(1ll*R*(R+1)/2)*(Pre[L]*(I[q]-I[p-1])+(J[q]-J[p-1])*(1ll*L*(L+1)/2));
		}
		return res;
	};
	if(l!=r)res+=wrk(l,r)+wrk(r,l);
	else res+=wrk(l,r)*2;
	return res;
}
void solve() {
	int l,r;
	cin>>l>>r;
	cout<<qp(g,(calc(r,r)-calc(l-1,r)-calc(r,l-1)+calc(l-1,l-1)).val)<<'\n';
}
bool Med;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t>>n;
	for(int i=0,nw=1; i<mod-1; ++i,nw=1ll*nw*g%mod)if(nw<=n)w[nw]=i;
	rep(i,1,n)W[i]=W[i-1]+w[i];
	rep(i,1,n)Pre[i]=Pre[i-1]+w[i]*i; 
	getprime(n);
	while(t--)solve();
	return 0;
}

P7486 「Stoi2031」彩虹题解

文章操作

相关推荐

评论

P7486 「Stoi2031」彩虹题解