题解 P3704 【[SDOI2017]数字表格】

· · 题解

前置知识：莫比乌斯反演，数论分块

题意

\prod_{i=1}^n \prod_{j=1}^m f_{ gcd(i,j) }

其中f为斐波拉契数列

Part 1.正常操作

$$\prod_{k=1}^d\prod_{i=1}^n\prod_{j=1}^mf_k^{[ gcd(i,j)==k ]}$$ 将重复的$f_k$计算到一起 $$\prod_{k=1}^df_k^{\sum_{i=1}^n\sum_{j=1}^m[ gcd(i,j)==k ]}$$ $$\prod_{k=1}^df_k^{\sum_{i=1}^{ \lfloor n / k \rfloor }\sum_{j=1}^{ \lfloor m / k \rfloor }[ gcd(i,j)==1 ]}$$ ## Part2.毒瘤操作 将指数部分拿出来看： $$\sum_{i=1}^{ \lfloor n / k \rfloor }\sum_{j=1}^{ \lfloor m / k \rfloor }[ gcd(i,j)==1 ]$$ 有一个结论： $$\sum_{i \mid n}\mu(i)=[n=1]$$ 证明如下： 1.当$n=1$时显然 2.当$n!=1$时，由唯一分解定理得：$n=p_1^{w_1}p_2^{w_2}...p_k^{w_k}

由莫比乌斯函数的性质，\mu(k) \not= 0当且仅当k无平方因子。(由多个质因子相乘)

有i个质因子的数有C_k^i种取值。

所以只需证

\sum_{i=0}^k(-1)^iC_k^i=0

很像二项式定理，将 x = 1 , y = -1 代入即可得证。

代入上式

\sum_{i=1}^{ \lfloor n / k \rfloor }\sum_{j=1}^{ \lfloor m / k \rfloor }\sum_{s \mid gcd(i,j)}\mu(s)

改写一下：

\sum_{i=1}^{ \lfloor n / k \rfloor }\sum_{j=1}^{ \lfloor m / k \rfloor }\sum_{s=1}^{ \lfloor n/k \rfloor }\mu(s)* [s \mid gcd(i,j)]

将\mu(s)向前提：

\sum_{s=1}^{ \lfloor n/k \rfloor } \mu(s) \sum_{i=1}^{ \lfloor n / k \rfloor }\sum_{j=1}^{ \lfloor m / k \rfloor }[s \mid gcd(i,j)] \sum_{s=1}^{ \lfloor n/k \rfloor } \mu(s)\lfloor \frac{n}{ks} \rfloor \lfloor \frac{m}{ks} \rfloor

然后，我们得到最终结果为：

\prod_{k=1}^df_k^{\sum_{s=1}^{ \lfloor n/k \rfloor } \mu(s)\lfloor \frac{n}{ks} \rfloor \lfloor \frac{m}{ks} \rfloor}

令T=ks，则原式等价于：

\prod_{T=1}^d\prod_{k \mid T }f_k^{\mu(\frac{T}{k})\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor} $$\prod_{T=1}^d(\prod_{k \mid T }f_k^{\mu(\frac{T}{k})})^{\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor}$$ 然后令$F(T)=\prod_{k \mid T }f_k^{\mu(\frac{T}{k})}$,原式化为 $$ \prod_{T=1}^dF(T)^{\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor} $$ 似乎就不能化简了 ## Part3.求解 内部的$F(k)$可以用类似埃筛的思想解决，外部用数论分块，就可以$\Theta(\sqrt{n})$解决了 ```cpp #include <cstdio> #include <iostream> using namespace std; #define Mod 1000000007 const int MAXN = 1000000; int k , prime[ MAXN / 10 + 5 ] , mu[ MAXN + 5 ]; bool vis[ MAXN + 5 ]; void sieve( int x ) { mu[ 1 ] = 1; for( int i = 2 ; i <= x ; i ++ ) { if( !vis[ i ] ) { prime[ ++ k ] = i; mu[ i ] = -1; } for( int j = 1 ; j <= k && 1ll * i * prime[ j ] <= x ; j ++ ) { vis[ i * prime[ j ] ] = 1; if( i % prime[ j ] == 0 ) break; mu[ i * prime[ j ] ] = -mu[ i ]; } } } int Quick_pow( int x , int po ) { int Ans = 1; while( po ) { if( po % 2 ) Ans = 1ll * Ans * x % Mod; x = 1ll * x * x % Mod; po /= 2; } return Ans; } int Inv( int x ) { return Quick_pow( x , Mod - 2 ); } int t , n , m; int f[ MAXN + 5 ] = { 0 , 1 , 1 } , finv[ MAXN + 5 ] = { 0 , 1 , 1 } , F[ MAXN + 5 ]; void Init( ) { sieve( MAXN ); for( int i = 3 ; i <= MAXN ; i ++ ) { f[ i ] = ( f[ i - 1 ] + f[ i - 2 ] ) % Mod; finv[ i ] = Inv( f[ i ] ); } for( int i = 0 ; i <= MAXN ; i ++ ) F[ i ] = 1; for( int i = 1 ; i <= MAXN ; i ++ ) { if( !mu[ i ] ) continue; for( int j = i ; j <= MAXN ; j += i ) F[ j ] = ( 1ll * F[ j ] * ( mu[ i ] == 1 ? f[ j / i ] : finv[ j / i ] ) ) % Mod; } for( int i = 2 ; i <= MAXN ; i ++ ) F[ i ] = 1ll * F[ i - 1 ] * F[ i ] % Mod; } int solve( int n , int m ) { int d = n < m ? n : m , Ans = 1; for( int l = 1 , r ; l <= d ; l = r + 1 ) { r = min( n / ( n / l ) , m / ( m / l ) ); Ans = 1ll * Ans * Quick_pow( 1ll * F[ r ] * Inv( F[ l - 1 ] ) % Mod , 1ll * ( n / l ) * ( m / l ) % ( Mod - 1 ) ) % Mod; } return ( Ans + Mod ) % Mod; } int main( ) { Init( ); scanf("%d",&t); while( t -- ) { scanf("%d %d",&n,&m); printf("%d\n",solve( n , m )); } return 0; } ```