BZOJ-4816: [Sdoi2017]数字表格

Description

设f[x]表示斐波那契数列的第x项的值，求有多组测试数据 T<=1000,1<=n,m<=10^6

推式子~（显然fibonacci数列没有什么性质）





将枚举d和他的约数，求出前缀乘积，然后分块求指数，底数为前缀乘积，求个逆元。时间复杂度：O(nlnn+T√nlogn)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
int mu[1001000],f[1001000];
int pri[501000],cnt;
ll d[1001000];
bool v[1001000];
inline ll Pow(ll x,ll y)
{
    ll re=1;
    while(y)
    {
        if(y&1) re=re*x%mod;
        x=x*x%mod; y>>=1;
    }
    return re;
}
inline void initialize()
{
    mu[1]=1; int i,j,k;
    for(i=2;i<=1000000;++i)
    {
        if(!v[i]) pri[++cnt]=i,mu[i]=-1;
        for(j=1;i*pri[j]<=1000000&&j<=cnt;++j)
        {
            v[i*pri[j]]=1;
            if(i%pri[j]) mu[i*pri[j]]=-mu[i];
            else {mu[i*pri[j]]=0; break;}
        }
    }
    f[0]=0; f[1]=1; ll Inv;
    for(i=2;i<=1000000;++i) f[i]=(f[i-1]+f[i-2])%mod;
    for(i=0;i<=1000000;++i) d[i]=1; 
    for(i=1;i<=1000000;++i)
    {
        Inv=Pow(f[i],mod-2);
        for(j=i,k=1;j<=1000000;j+=i,++k)
            if(mu[k]) d[j]= (~mu[k]) ? d[j]*f[i]%mod:d[j]*Inv%mod;
    }
    for(i=1;i<=1000000;++i)
        d[i]=d[i]*d[i-1]%mod;
}
int main()
{
    initialize();
    int T,n,m; scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m); if(n>m) swap(n,m);
        ll b=1,e,ans=1;
        while(b<=n)
        {
            e=min(n/(n/b),m/(m/b));
            ans=ans*Pow(d[e]*Pow(d[b-1],mod-2)%mod,(n/b)*(m/b)%(mod-1))%mod;
            b=e+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}