1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
| #include <cstdio> #include <algorithm> using namespace std; template <class Type> void read (Type &x) { char c; bool flag = false; while ((c = getchar()) < '0' || c > '9') c == '-' && (flag = true); x = c - '0'; while ((c = getchar()) >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - '0'; flag && (x = ~x + 1); } template <class Type, class ...rest> void read (Type &x, rest &...y) { read(x), read(y...); } template <class Type> void write (Type x) { x < 0 && (putchar('-'), x = ~x + 1); x > 9 && (write(x / 10), 0); putchar('0' + x % 10); } typedef long long LL; const int N = 1e6 + 10, mod = 32465177; bool vis[N]; int cnt, p[N], mu[N], s[N], f[N], g[N], h[N]; int binpow (int b, int k = mod - 2) { (k %= mod - 1) += mod - 1; int res = 1; for (; k; k >>= 1, b = (LL)b * b % mod) if (k & 1) res = (LL)res * b % mod; return res; } void init () { vis[1] = true; mu[1] = 1; for (int i = 2; i < N; ++i) { if (!vis[i]) mu[p[++cnt] = i] = -1; for (int j = 1; j <= cnt && i * p[j] < N; ++j) { vis[i * p[j]] = true; if (i % p[j] == 0) break; mu[i * p[j]] = -mu[i]; } } for (int i = 1; i < N; ++i) s[i] = (s[i - 1] + i) % (mod - 1); f[0] = 1; for (int i = 1; i < N; ++i) f[i] = (LL)f[i - 1] * binpow(i, i) % mod; for (int i = 1; i < N; ++i) if (mu[i]) for (int j = i, t = i * mu[i]; j < N; j += i) (g[j] += t) %= (mod - 1); for (int i = 0; i < N; ++i) h[i] = 1; for (int i = 1; i < N; ++i) if (mu[i]) for (int j = i, t = binpow(i, i * mu[i]); j < N; j += i) h[j] = (LL)h[j] * t % mod; for (int i = 1; i < N; ++i) h[i] = (LL)h[i - 1] * binpow((LL)binpow(i, g[i]) * h[i] % mod, i) % mod; for (int i = 1; i < N; ++i) g[i] = (g[i - 1] + (LL)g[i] * i) % (mod - 1); } int calc (int n, int m) { int res = 1; for (int l = 1, r; l <= n; l = r + 1) { int a = n / l, b = m / l; r = min(n / a, m / b); res = (LL)binpow((LL)binpow(f[a], s[b]) * binpow(f[b], s[a]) % mod, g[r] - g[l - 1]) * binpow((LL)h[r] * binpow(h[l - 1]) % mod, (LL)s[a] * s[b] % (mod - 1)) % mod * res % mod; } return res; } int main () { init(); int T; read(T); scanf("%*d"); for (int l, r; T; --T, puts("")) { read(l, r); --l; write(((LL)calc(r, r) * calc(l, l) % mod * binpow(binpow(calc(l, r)), 2) % mod + mod) % mod); } return 0; }
|
Gitalk 加载中 ...