P3704

发表于 分类于
[SDOI2017]数字表格

[SDOI2017]数字表格

很有意思的题目。

这题最大的特点应该就是这个 $\prod$，这个东西和一般的 $\sum$ 套路有所不同。

但实际上除了这个，剩下的技巧都是很基础的莫比乌斯反演技巧。

先假设 $m\le n$。

直接开推：

$$\begin{aligned}& \prod_{i=1}^{n}\prod_{j=1}^{m}f(\gcd(i,j))\\ = & \prod_{i=1}^{n}\prod_{j=1}^{m}\prod_{d\in[1,m],\gcd(i,j)=d}f(d)\\ = & \prod_{d=1}^{m}\prod_{i=1}^{\lfloor\frac{n}{d}\rfloor}\prod_{j=1}^{\lfloor\frac{m}{d}\rfloor}\prod_{\gcd(i,j)=1}f(d)\end{aligned}$$

我们上面的步骤全部只是在变化枚举顺序，对枚举的元素都没有作任何改动。

下面我们就要利用到 $\prod$ 的意义。

可以想到，$\prod_{i=1}^{n}x=x^n$，这很显然。

所以我们可以把 $\prod$ 转化为幂次数来处理。

$$\begin{aligned}= & \prod_{d=1}^{m}f(d)^{\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)=1]}\\ =& \prod_{d=1}^{m}f(d)^{\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{k\mid \gcd(i,j)}\mu(k)}\\ = & \prod_{d=1}^{m}f(d)^{\sum_{k=1}^{\lfloor\frac{m}{d}\rfloor}\mu(k)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor}\end{aligned}$$

下面我们要把 $k$ 提到前面枚举，同样利用上面我们的幂次数与 $\prod$ 的转化。

$$\begin{aligned}= & \prod_{k=1}^{m}\prod_{d=1}^{\lfloor\frac{m}{k}\rfloor}f(d)^{\mu(k)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor}\end{aligned}$$

接下来我们设 $T=kd$，则 $k=\dfrac{T}{d}$，于是有：

$$\begin{aligned}= & \prod_{T=1}^{m}\prod_{d\mid T}f(d)^{\mu(\frac{T}{d})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor} \\ = & \prod_{T=1}^{m}(\prod_{d\mid T}f(d)^{\mu(\frac{T}{d})})^{\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor}\end{aligned}$$

现在我们设 $f_{pre}(T)=\prod_{d\mid T}f(d)^{\mu(\frac{T}{d})}$。

上面的那个函数我们可以先枚举 $d$ 再枚举 $T$，用埃氏筛在 $O(m\ln m\log mo)$ 的复杂度下预处理。后面乘上 $\log mo$ 是当 $\mu(\dfrac{T}{d})=-1$ 时求逆元的复杂度。

然后我们设前缀乘函数 $cf_{pre}(n)=\prod_{i=1}^{n}f_{pre}(i)$。

然后上面我们的式子就可以整除分块了。

最后复杂度是 $O(m\ln m\log mo+T\sqrt{m}\log mo)$。

然后我提几个细节。

首先，为什么我们在求 $f_{pre}$ 的时候可以用费马小定理求一些斐波那契数的逆元？我不会严谨证，但是我写了个 check 程序检验了前 $10^6$ 个斐波那契数是否与 $10^9+7$ 互质，结果是全部都互质。

其次是关于这个次数 $\lfloor\dfrac{m}{T}\rfloor\lfloor\dfrac{n}{T}\rfloor$，这个次数可能比较大，为了一定程度保证复杂度，我们使用扩展欧拉定理。

给一下扩展欧拉定理的内容，若 $b>\varphi(p)$，则有：

$$a^b\equiv a^{b\bmod \varphi(p)+
\varphi(p)}\pmod{p}$$

没了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=1e6,mo=1e9+7;

ll T,n,m,cnt;

ll fib[N+5],prime[N+5],mu[N+5],pf[N+5],cpf[N+5];
bool f[N+5];

inline ll qpow(ll b,ll p) {
  ll res=1;while(p) {if(p&1) res=res*b%mo;b=b*b%mo;p>>=1;}return res;
}

inline void Init() {
  mu[1]=1;f[1]=1;
  for(ll i=2;i<=N;i++) {
    if(!f[i]) {prime[++cnt]=i;mu[i]=-1;}
    for(ll j=1;j<=cnt&&i*prime[j]<=N;j++) {
      f[i*prime[j]]=1;
      if(i%prime[j]==0) {mu[i*prime[j]]=0;break;}
      mu[i*prime[j]]=-mu[i];
    }
  }
  fib[1]=1;for(ll i=2;i<=N;i++) fib[i]=(fib[i-1]+fib[i-2])%mo;
  for(ll i=1;i<=N;i++) pf[i]=1;
  for(ll i=1;i<=N;i++) {
    for(ll j=i,q=1;j<=N;j+=i,q++) {
      if(mu[q]==-1) pf[j]=pf[j]*qpow(fib[i],mo-2)%mo;
      if(mu[q]==1) pf[j]=pf[j]*fib[i]%mo;
    }
  }
  cpf[0]=1;
  for(ll i=1;i<=N;i++) {
    cpf[i]=cpf[i-1]*pf[i]%mo;
  }
}

inline ll read() {
  ll ret=0,f=1;char ch=getchar();
  while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
  while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
  return ret*f;
}

inline void write(ll x) {
  static char buf[22];static ll len=-1;
  if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
  else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
  while(len>=0) putchar(buf[len--]);
}

inline void writeln(ll x) {write(x);putchar(10);}

int main() {

  Init();

  T=read();

  while(T--) {
    n=read();m=read();if(n<m) swap(n,m);
    ll ans=1;
    for(ll i=1,j;i<=m;i=j+1) {
      j=min(n/(n/i),m/(m/i));
      ll tmp=(n/i)*(m/i);
      ans=ans*
      qpow(cpf[j]*qpow(cpf[i-1],mo-2)%mo,tmp>mo-1?tmp%(mo-1)+mo-1:tmp)%mo;
    }
    writeln(ans);
  }

  return 0;
}