P3704数字表格(莫比乌斯反演)

?

题目背景

Doris 刚刚学习了 fibonacci 数列。用?fi??表示数列的第?i?项，那么

0=0,1=1f0?=0,f1?=1

fn?=fn?1?+fn?2?,n≥2

题目描述

Doris 用老师的超级计算机生成了一个?n×m?的表格，

第?i?行第?j?列的格子中的数是?gcd(i,j)?，其中gcd(i,j)?表示?i,j?的最大公约数。

Doris 的表格中共有?n×m?个数，她想知道这些数的乘积是多少。

答案对?109+7?取模。

输入格式

本题单个测试点内有多组测试数据。

输入的第一行是一个整数?T，表示测试数据的组数。

接下来?T?行，每行两个整数?n,m，表示一组数据。

输出格式

对于每组数据，输出一行一个整数表示答案。

输入输出样例

输入 #1复制

3
2 3
4 5
6 7

输出 #1复制

1
6
960

思路：

代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const double eps = 1e-8;
const int N = 1e6+10;
const long long ?mod =1e9+7;
#define LL long long?
int pre[N],st[N];
int n,cn,m;
LL mu[N],ff[N],gg[N],F[N];
LL g(int l, int k)
{
? ? return (LL)k / (k / l);
}
LL quick(LL x, LL y,LL mod)
{
? ? LL ans = 1;
? ? while (y)
? ? {
? ? ? ? if (y & 1)
? ? ? ? ? ? ans = ans * x % mod;
? ? ? ? y = y >> 1;
? ? ? ? x = x * x % mod;
? ? }
? ? return ans;
}
void into()
{
? ? mu[1] = 1;
? ? for (int i = 2; i < N; i++)
? ? {
? ? ? ? if (!st[i]) pre[++cn] = i, mu[i] = -1;
? ? ? ? for (int j = 1; pre[j] * i < N && j <= cn; j++)
? ? ? ? {
? ? ? ? ? ? st[pre[j] * i] = 1;
? ? ? ? ? ? if (i % pre[j] == 0) break;
? ? ? ? ? ? mu[i * pre[j]] = -mu[i];
? ? ? ? }
? ? }
? ? ? ?F[0]=F[1]=gg[1]=ff[1] = 1;
? ? ? ? for (int i = 2; i < N; i++)
? ? ? ? {
? ? ? ? ? ? ff[i] = (ff[i - 2] + ff[i - 1]) % mod;
? ? ? ? ? ? gg[i] = quick(ff[i], mod - 2,mod);
? ? ? ? ? ? F[i] = 1;
? ? ? ? }
? ? ? ? ? ? for(int i=1;i<N;i++)
? ? ? ? ? ?for (int j = i; j < N; j += i)
? ? ? ? ? ?{
? ? ? ? ? ? ? ?if (mu[j/i] == 1)
? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ?F[j] = (LL)F[j] * ff[i] % mod;
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?else if (mu[j/i] == -1)
? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ?F[j] = (LL)F[j] * gg[i] % mod;
? ? ? ? ? ? ? ?}
? ? ? ? ? ?}
? ? ? ?for (int i = 1; i < N; i++)
? ? ? ? ? ?F[i] = (LL)F[i] * F[i - 1] % mod;
}
int main()
{
? ? into();
? ? int T;
? ? cin >> T;
? ? while (T--)
? ? {
? ? ? ? cin >> n >> m;
? ? ? ? if (n > m)swap(n, m);
? ? ? ? LL ans = 1;
? ? ? ? for (int l = 1, r; l <= n; l = r + 1)
? ? ? ? {
? ? ? ? ? ? r = min(n, (int)min(g(l, n), g(l, m)));
? ? ? ? ? ? LL s = (LL)F[r] * quick(F[l - 1], mod - 2, mod) % mod;
? ? ? ? ? ? ans = (LL)ans * quick(s, (LL)(n / l) * (m / l) % (mod - 1),mod) % mod;
? ? ? ? }
? ? ? ? cout << (ans % mod + mod) % mod << endl;
? ? }
??
? ? return 0;
}?