- //By SiriusRen
- #include#include#include using namespace std;
- const int N = 1000005,
- mod = 1000000007;
- int n,
- m,
- cases,
- f[N],
- vis[N],
- prime[N],
- g[N],
- mu[N],
- tot;
- typedef long long ll;
- int pow(ll x, int y) {
- ll res = 1;
- while (y) {
- if (y & 1) res = res * x % mod;
- x = x * x % mod,
- y >>= 1;
- }
- return res;
- }
- void shai() {
- mu[1] = f[1] = g[0] = 1;
- for (int i = 2; i) {
- if (!vis[i]) mu[i] = -1,
- prime[++tot] = i;
- for (int j = 1; i * prime[j]) {
- vis[i * prime[j]] = 1,
- mu[i * prime[j]] = -mu[i];
- if (i % prime[j] == 0) {
- mu[i * prime[j]] = 0;
- break;
- }
- }
- f[i] = (f[i - 1] + f[i - 2]) % mod;
- }
- for (int i = 1; i1;
- for (int i = 1; i) {
- int ni = pow(f[i], mod - 2);
- for (int j = 1; i * j) {
- if (mu[j] == 1) g[i * j] = (1ll * g[i * j] * f[i]) % mod;
- else if (mu[j] == -1) g[i * j] = (1ll * g[i * j] * ni) % mod;
- }
- }
- for (int i = 1; i1]) % mod;
- }
- int main() {
- shai();
- scanf("%d", &cases);
- while (cases--) {
- scanf("%d%d", &n, &m);
- if (n > m) swap(n, m);
- ll ans = 1;
- for (int l = 1, r; l <= n; l = r + 1) {
- r = min(n / (n / l), m / (m / l));
- ans = ans * pow(1ll * g[r] * pow(g[l - 1], mod - 2) % mod, 1ll * (n / l) * (m / l) % (mod - 1)) % mod;
- }
- printf("%lld\n", ans);
- }
- }
来源: http://www.bubuko.com/infodetail-2022730.html