自动搬运

查看原文

来自洛谷，原作者为

	lqhsr ☝这个家伙很♂，✓什么也没有留↓

搬运于2025-08-24 22:05:06，当前版本为作者最后更新于2019-10-20 22:40:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

upd:10.21 LaTeX不支持多行，于是公式挂了，改成图片好了

写这篇题解的目的：

1.分享一种目前最优解的做法

2.分享一些卡常的乱(hao)搞(sao)做法

还是先讲做法吧

首先我们拿到这道题(一看就是一道数学题)

由于式子过于复杂，暴力得$n^2$显然稳T

于是我们考虑拆式子

把第二个$\prod$变成$\sum$并丢到指数位置是因为$x^a*x^b=x^{a+b}$

想到这里就可以做了

我们记录每个i的答案，最后直接用B的答案除以A-1的答案就行(A-1是因为答案是累乘起来的，类比于前缀和)

其实我们可以从i每次变化入手

举个例子

i=3
sum=3/1+3/2+3/3
ans=3  +1  +1	
i=4
sum=4/1+4/2+4/3+4/4
ans=4  +2  +1  +1
i=5
sum=5/1+5/2+5/3+5/4+5/5
ans=5  +2  +1  +1  +1
i=6
sum=6/1+6/2+6/3+6/4+6/5+6/6
ans=6  +3  +2  +1  +1  +1

说说你都发现了什么

->ans[i]相比ans[i-1]于在每个i的约数的位置+1了！！！

然后就可以递推求了ans[i]

对于i我们在i+1时乘上i+1的约数个数

对于inv(j)我们没次在i+1时把$prod[j]$乘上$prod[k](j \mod k==0)$

期望得分: 75 or 100

我的提交：用时1.76s内存34.91MB,TLE on Sub 4 #16、#17、#20

开始卡常啦

其实sub4TLE只是你少了几个无用的for循环

卡常1：加上 register and inline ，i++变++i

还真的有用少T一个点：用时1.77s内存34.91MB,但是TLE on Sub 4 #16 #20

卡常2：听说可以展开循环来刺激CPU

实践证明这是真的：用时1.72s内存34.99MB,TLE on Sub 4 #16

卡常3：是不是展开的不够，再加几个无用的for试试

究竟是什么神仙操作，将一份TLE代码挽救于水深火热之中？？？

那就是：

	for(int i=1;i<=100000;i++);
	for(int i=1;i<=100000;i++);
	for(int i=1;i<=100000;i++);

对！！！你没有看错！！！就是他！！！

用时1.66s内存34.87MB,AC

卡常4：发现上面的方(cao)法(zuo)只是有时能过有时过不了

再仔细一想，整个程序里面最慢的莫过于取模运算了，于是想到取模优化

用时929ms内存35.04MB,AC

给出最终代码

#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
int tt,a[1000006],b[1000006],cnt[1000005],maxn;
const int mod=19260817;
ll ans[1000005],inv[1000005],prod[1000005];
inline int read(){
	register int x=0;register char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
inline ll mul(ll x,ll y){
    ll re=x*y;
    re-=re/mod*mod;//本来想用while实现 但运行之后发现比直接%还慢
    return re;
}
inline ll quick(ll x,ll p){
	register ll re=1;
	while(p){
		if(p&1)re=mul(re,x);
		p>>=1;
		x=mul(x,x);
	}
	return re;
}
inline void exgcd(ll aa,ll bb,ll &x,ll &y){
	if(!bb){x=1,y=0;return ;}
	exgcd(bb,aa%bb,y,x);
	y-=aa/bb*x;
}
inline ll getinv(ll k){
	ll x,y;
	exgcd(k,mod,x,y);
	x=(x%mod+mod)%mod;
	return x;
}
int main(){
	tt=read();
	for(int i=1;i<=100000;i++);
	for(int i=1;i<=100000;i++);
	for(int i=1;i<=100000;i++);
	for(register int i=1;i<=tt;++i)a[i]=read(),b[i]=read();
	for(int i=1;i<=tt;i++)maxn=maxn>b[i]?maxn:b[i];
	inv[1]=1,prod[1]=1;
	for(register int i=2;i<=maxn;++i){
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	}
	for(register int i=1;i<=maxn;i++)prod[i]=1;
	for(register int i=1;i<=maxn;++i)
		for(register int j=i;j<=maxn;j+=i)
			++cnt[j];
	for(register int i=1;i<=maxn;++i)
		for(register int j=i;j<=maxn;j+=i)
			prod[j]=mul(prod[j],inv[i]);
	register ll now=0;
	prod[0]=1,ans[0]=1;
	for(register int i=1;i<=maxn;i++)cnt[i]+=cnt[i-1];
	for(register int i=1;i<=maxn;i++)prod[i]=mul(prod[i],prod[i-1]);
	for(register int i=1;i<=maxn;++i)ans[i]=mul(ans[i-1],mul(quick(i,cnt[i]),prod[i]))%mod;
	for(register int i=1;i<=tt;++i)printf("%lld\n",mul(ans[b[i]],getinv(ans[a[i]-1])));
}