zcmimi's blog
avatar
zc
2020-03-15 15:48:00
  • 本文总阅读量
查看原题

点击跳转

n<m \prod_{i=1}^n \prod_{j=1}^m f_{\gcd(i,j)} \\ =\prod_{d=1}^n{f_d}^{\sum_{i=1}^n \sum_{j=1}^m[\gcd(i,j)=d]} \\ =\prod_{d=1}^n{f_d}^{\sum_{i=1}^{\left \lfloor \frac nd \right \rfloor} \sum_{j=1}^{\left \lfloor \frac md \right \rfloor}[\gcd(i,j)=1]} \\ =\prod_{d=1}^n{f_d}^{\sum_{i=1}^{\left \lfloor \frac nd \right \rfloor} \mu(i) \left \lfloor \frac n{id}\right \rfloor \left \lfloor \frac m{id}\right \rfloor}

数论分块套数论分块会tle,继续老套路优化

T=id

=\prod_{T=1}^n\sum_{d|T}{f_d}^{\mu(\frac Td) \left \lfloor \frac n{T}\right \rfloor \left \lfloor \frac m{T}\right \rfloor}

可以先预处理出函数s(T)=\sum_{d|T}{f_d}^{\mu(\frac Td)}的前缀积

然后就可以做到数论分块O(\sqrt n)的复杂度了

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(3)
#define il __inline__ __attribute__ ((always_inline))
namespace IO{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;il char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}il void in(char &ch){if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)__=1;else ch=c;}il void in(char *ch){*ch='\0';if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF){__=1;return;}*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)__=1;*ch='\0';}template<typename T>il void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>il void in(T &x,arr & ... y){in(x),in(y...);}const char ln='\n';static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;il void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}il void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}il void out(const char* s){while(*s)pt(*s++);}il void out(char* s){while(*s)pt(*s++);}il void out(char c){pt(c);}template<typename T>il void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>il void out(T x,arr & ... y){out(x),out(y...);}}using namespace IO;
il int min(int x,int y){return x<y?x:y;}
const int N=1000000,P=1000000007;
int n,cnt=0,pri[78500],mu[N+11],f[N+11],g[N+11],s[N+11];
bool b[N+11];
il int pw(int x,int b){
    int ans=1;
    while(b){
        if(b&1)ans=1ll*ans*x%P;
        b>>=1;x=1ll*x*x%P;
    }
    return ans;
}
il int inv(int x){return pw(x,P-2);}
int main(){
    mu[1]=f[1]=g[1]=s[0]=s[1]=1;
    for(int i=2;i<=N;++i){
        f[i]=(f[i-1]+f[i-2])%P;
        g[i]=inv(f[i]);
        s[i]=1;
        if(!b[i])pri[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt&&i*pri[j]<=N;++j){
            b[i*pri[j]]=1;
            if(i%pri[j])mu[i*pri[j]]=-mu[i];
            else break;
        }
    }
    for(int i=1;i<=N;++i)
    if(mu[i])for(int j=i;j<=N;j+=i)
         s[j]=1ll*s[j]*(~mu[i]?f[j/i]:g[j/i])%P;
    for(int i=2;i<=N;++i)s[i]=1ll*s[i]*s[i-1]%P;
    int T;in(T);
    while(T--){
        int n,m,ans=1;
        in(n,m);
        if(n>m)n^=m,m^=n,n^=m;
        for(int l=1,r;l<=n;l=r+1){
            r=min(n/(n/l),m/(m/l));
            ans=1ll*ans*pw(1ll*s[r]*inv(s[l-1])%P,1ll*(n/l)*(m/l)%(P-1))%P;
        }
        out(ans,ln);
    }
    flush();
}
LG 3704 [SDOI2017]数字表格
comment评论
Search
search