题解 P4902 【乘积】

· · 题解

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])));
}