[SDOI2017] 数字表格
程序员文章站
2022-05-14 08:43:15
反演拾遗,设'~'表示min(n,m),推狮子 $$ \prod_{i=1}^n\prod_{j=1}^n\mathbb{fib}_{\gcd(a,b)} =\prod_{d=1}^\sim\mathbb{pow}(\mathbb{fib}_d,\sum_{i=1}^{n/d}\sum_{j=1}^ ......
反演拾遗,设'~'表示min(n,m),推狮子
\[
\prod_{i=1}^n\prod_{j=1}^n\mathbb{fib}_{\gcd(a,b)}
=\prod_{d=1}^\sim\mathbb{pow}(\mathbb{fib}_d,\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\epsilon(\gcd(n,m)))\\
=\prod_{d=1}^\sim\mathbb{pow}(\mathbb{fib}_d,\sum_{t=1}^{\sim/d}\mu(t)\frac{n}{dt}\frac{m}{dt})\\
=\prod_{q=1}^\sim\prod_{d|q}\mathbb{pow}(\mathbb{fib}_d,\mu(\frac{q}{d})\frac{n}{q}\frac{m}{q})\\
=\prod_{q=1}^\sim\mathbb{pow}(\prod_{d|q}\mathbb{pow}(\mathbb{fib}_d,\mu(\frac{q}{d})),\frac{n}{q}\frac{m}{q})
\]
预处理处外层pow的底数设为w[q],求其前缀积,每组询问分块。
#include <bits/stdc++.h> #define ll long long using namespace std; const int n=1e6+10; const int p=1e9+7; inline int qpow(ll x,ll y) { int c=1; for(; y; y>>=1,x=x*x%p) if(y&1) c=x*c%p; return c; } int pri[n],mu[n],fib[n],fiv[n],cnt; long long w[n]; bool vis[n]; void initial() { mu[1]=1; for(int i=2; i<n; ++i) { if(!vis[i]) pri[++cnt]=i,mu[i]=-1; for(int j=1; j<=cnt&&i*pri[j]<n; ++j) { vis[i*pri[j]]=1; if(i%pri[j]==0) break; else mu[i*pri[j]]=-mu[i]; } } fib[1]=w[0]=w[1]=fiv[0]=fiv[1]=1; for(int i=2; i<n; ++i) { fib[i]=(fib[i-1]+fib[i-2])%p; fiv[i]=qpow(fib[i],p-2); w[i]=1; } for(int d=1; d<n; ++d) { for(int q=d; q<n; q+=d) { if(mu[q/d]>0) w[q]=w[q]*fib[d]%p; else if(mu[q/d]<0) w[q]=w[q]*fiv[d]%p; } w[d]=w[d-1]*w[d]%p; } } int main() { initial(); //0.32s int t,n,m; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); int c=1,sim=min(n,m); for(int l=1,r; l<=sim; l=r+1) { r=min(n/(n/l),m/(m/l)); c=1ll*c*qpow(w[r]*qpow(w[l-1],p-2)%p,1ll*n/l*(m/l)%(p-1))%p; } printf("%d\n",c); } return 0; }
把\(\mu\)求成\(\varphi\)是要闹哪样啊
下一篇: C语言编程笔记丨如何在指针中隐藏数据?