bzoj 4816 [Sdoi2017]数字表格—

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4816

\( ans=\prod\limits_{d=1}^{n}f[d]^{\sum\limits_{l=1}^{\frac{n}{d}}\left\lfloor\frac{n}{l*d}\right\rfloor*\left\lfloor\frac{m}{l*d}\right\rfloor} \)

　　\(=\prod\limits_{D=1}^{n}\prod\limits_{d|D}f[d]^{\mu(\frac{D}{d})*\left\lfloor\frac{n}{D}\right\rfloor*\left\lfloor\frac{m}{D}\right\rfloor} \)

令 \( g(D)=\prod\limits_{d|D}f(d)^{\mu(\frac{D}{d})} \) ，就能做了。预处理 g 不要 \( \sqrt{n} \) 枚举约数，而 n*ln(n) 枚举倍数。

预处理 g 的前缀积的逆元，回答询问的时候就少一个 log 。

注意指数上是模 (mod-1) ！！！

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=1e6+,mod=1e9+;

int g[N],s[N],sn[N],u[N],pri[N];bool vis[N];

int pw(int x,int k)

{int ret=;while(k){if(k&)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=;}return ret;}

void init()

{

  int f0=,f1=,lm=1e6,cnt=;

  u[]=;

  for(int i=;i<=lm;i++)

    {

      if(!vis[i])pri[++cnt]=i,u[i]=-;

      for(int j=;j<=cnt&&(ll)i*pri[j]<=lm;j++)

    {

      vis[i*pri[j]]=;

      if(i%pri[j]==){u[i*pri[j]]=;break;}

      u[i*pri[j]]=-u[i];

    }

    }

  for(int j=;j<=lm;j++)g[j]=;

  s[]=;

  for(int i=;i<=lm;i++)

    {

      swap(f0,f1);f1+=f0;if(f1>=mod)f1-=mod;

      int inv=pw(f1,mod-);

      for(int j=i,k=;j<=lm;j+=i,k++)

    if(u[k]==)g[j]=(ll)g[j]*f1%mod;

    else if(u[k]==-)g[j]=(ll)g[j]*inv%mod;

      s[i]=(ll)s[i-]*g[i]%mod;

    }

  sn[lm]=pw(s[lm],mod-);

  for(int i=lm-;i;i--)sn[i]=(ll)sn[i+]*g[i+]%mod;

  sn[]=;//

}

int main()

{

  int T,n,m;scanf("%d",&T);init();

  while(T--)

    {

      scanf("%d%d",&n,&m);if(n>m)swap(n,m);

      int ans=;

      for(int i=,j;i<=n;i=j+)

    {

      int d0=n/i,d1=m/i; j=min(n/d0,m/d1);

      ans=(ll)ans*pw((ll)s[j]*sn[i-]%mod,(ll)d0*d1%(mod-))%mod;/////%(mod-1)!!!!!

    }

      printf("%d\n",ans);

    }

  return ;

}

巴特西

bzoj 4816 [Sdoi2017]数字表格——反演

最新文章

热门文章