题意：求
\[ \prod_{i=1}^n \prod_{j=1}^m f[(i,j)] \]考场60分
其实多推一步就推倒了...
因为是乘，我们可以放到幂上
\[ \prod_{d=1}^n \prod_{i=1}^{\frac{n}{d}}\prod_{i=1}^{\frac{m}{d}} f[d]^{[(i,j)=1]} \] 套路一直推完\[ \prod_{D=1}^n \prod_{d|D} f[d]^{\mu(\frac{D}{d}) \cdot \frac{n}{D} \cdot \frac{m}{D}} \] 用枚举倍数的方法预处理\[ \prod_{d|D} f[d]^{\mu(\frac{D}{d})} \] 的前缀积就行了#include#include #include #include #include using namespace std;const int N=1e6+5, mo=1e9+7;typedef long long ll;inline int read() { char c=getchar(); int x=0, f=1; while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();} while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();} return x*f;}int Q, n, m, f[N]; ll g[N];inline ll Pow(ll a, int b) { ll ans=1; for(; b; b>>=1, a=a*a%mo) if(b&1) ans=ans*a%mo; return ans;}int p[N], notp[N]; ll mu[N];inline void mod(int &x) {if(x>=mo) x-=mo;}inline void mod(ll &x) {if(x>=mo) x-=mo;}void sieve(int n) { mu[1]=1; for(int i=2; i<=n; i++) { //printf("i %d\n",i); if(!notp[i]) p[++p[0]]=i, mu[i]=-1; for(int j=1; j<=p[0] && i*p[j]<=n; j++) { //printf("j %d\n",p[j]); notp[ i*p[j] ]=1; if(i % p[j] == 0) { mu[ i*p[j] ]=0; break; } mu[ i*p[j] ] = -mu[i]; } } f[0]=0; f[1]=1; g[1]=1; g[0]=1; for(int i=2; i<=n; i++) mod(f[i] += f[i-1] + f[i-2]), g[i] = 1; for(int i=1; i<=n; i++) { ll inv = Pow(f[i], mo-2); for(int j=i, k=1; j<=n; j+=i, k++) if(mu[k]) ( g[j] *= (mu[k]==1 ? f[i] : inv) ) %= mo; (g[i] *= g[i-1]) %= mo; } //for(int i=1; i<=10; i++) printf("fg %d %d %lld\n", i, f[i], g[i]);}void cal(int n, int m) { if(n>m) swap(n, m); ll ans=1; int r; for(int i=1; i<=n; i=r+1) { r = min(n/(n/i), m/(m/i)); ( ans *= Pow(g[r] * Pow(g[i-1], mo-2) %mo, (ll)(n/i) * (m/i) % (mo-1)) ) %= mo; } printf("%lld\n", ans);}int main() { freopen("product.in", "r", stdin); freopen("product.out", "w", stdout); sieve(N-1); Q=read(); for(int i=1; i<=Q; i++) { n=read(); m=read(); cal(n, m); }}