反恐精英加速挂,孙倩 高义,喷泉模型下载
反演拾遗，设'~'表示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\)是要闹哪样啊
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论