【题解】洛谷P4902[CYJian的水题大赛[第三弹]]C.乘积 线性筛
赛后题解
讲道理,中间那些公式变形看明白了,线性筛那段给我搞蒙了……h是算啥的,为啥要%(mod-1) QAQ
#include<cstdio>
const int mod=19260817,N=1e6+10;
int t,a,b,prime[N/10],p,d[N],h[N],f[N];
bool iscomp[N];
long long qpow(long long a,int b)
{
long long ret=1;
for(;b;b>>=1)
{
if(b&1)ret=ret*a%mod;
a=a*a%mod;
}
return ret;
}
void primetable()
{
for(int i=2;i<N;i++)
{
if(!iscomp[i])prime[p++]=i,d[i]=2,h[i]=i;
for(int j=0;j<p&&i*prime[j]<N;j++)
{
iscomp[i*prime[j]]=1;
if(i%prime[j]==0)
{
int tmp=i,cnt=2,F=1;
while(tmp%prime[j]==0)tmp/=prime[j],F+=cnt,cnt++;
d[i*prime[j]]=d[tmp]*cnt;
h[i*prime[j]]=1ll*qpow(h[tmp],d[i/tmp*prime[j]])*qpow(prime[j],1ll*F*d[tmp]%(mod-1))%mod;
break;
}
d[i*prime[j]]=d[i]*2;
h[i*prime[j]]=1ll*h[i]*h[i]%mod*qpow(prime[j],d[i])%mod;
}
}
}
void Init()
{
f[0]=f[1]=h[0]=h[1]=d[1]=1;primetable();
for(int i=2;i<N;i++)
{
d[i]+=d[i-1];
f[i]=1ll*f[i-1]*qpow(i,d[i]%(mod-1))%mod;
h[i]=1ll*h[i-1]*h[i]%mod;
}
for(int i=2;i<N;i++)
h[i]=1ll*h[i-1]*h[i]%mod;
}
int main()
{
Init();
scanf("%d",&t);
for(int i=1;i<=t;i++)
{
scanf("%d%d",&a,&b);
printf("%d\n",1ll*qpow(f[a-1],mod-2)*f[b]%mod*qpow(h[b],mod-2)%mod*h[a-1]%mod);
}
return 0;
}