欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【jzoj100006】【SDOI2017】【数字表格】【数论】

程序员文章站 2022-06-08 12:29:41
...

题目大意

【jzoj100006】【SDOI2017】【数字表格】【数论】

解题思路

考虑生成一个新的序列g,使得f[i]=Πd|i(d!=i)g[d]

ans=Πni=1Πmj=1f[gcd(i,j)]

=Πni=1Πmj=1Πd|gcd(i,j)(d!=gcd(i,j))g[d]

=Πmin(n,m)i=1g[i](n/i)(m/i)

我们可以处理出g的前缀积,对于指数一样的i一起处理。

code

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LF double
#define LL long long
#define ULL unsigned long long
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j,k) for(int i=begin[j][k];i;i=next[j][i])
using namespace std;
int const mn=1e6+9,mo=1e9+7,inf=1e9+7;
int t,n,m;
LL f[mn],g[mn],h[mn];
LL Pow(LL x,LL y){
    LL z=1;
    while(y){
        if(y&1)z=z*x%mo;
        x=x*x%mo;
        y>>=1;
    }
    return z;
}
int main(){
    //freopen("product.in","r",stdin);
    //freopen("product.out","w",stdout);
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    scanf("%d",&t);
    int lim=1e6;
    f[1]=g[0]=g[1]=h[0]=h[1]=1;
    fo(i,2,lim)g[i]=f[i]=(f[i-2]+f[i-1])%mo;
    fo(i,2,lim){
        LL tmp=Pow(g[i],mo-2);
        fo(j,2,lim/i)g[i*j]=g[i*j]*tmp%mo;
        g[i]=g[i]*g[i-1]%mo;
        h[i]=Pow(g[i],mo-2);
    }
    fo(cas,1,t){
        scanf("%d%d",&n,&m);
        if(n>m)swap(n,m);
        LL ans=1;
        for(int i=1,j;i<=n;i=j+1){
            j=min(n/(n/i),m/(m/i));
            ans=ans*Pow(g[j]*h[i-1]%mo,1ll*(n/i)*(m/i))%mo;
        }
        printf("%lld\n",ans);
    }
    return 0;
}