题解
数论好题，结合了卢卡斯定理，中国剩余定理，费马小定理。
网上题解很多这里就不细说了，数论我还是要加油呀！
代码
|
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 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
#include <bits/stdc++.h> using namespace std; const int MOD = 999911659; typedef long long ll; ll p[5] = {0, 2, 3, 4679, 35617}; ll fact[40003]; ll a[5]; ll exgcd(ll a, ll b, ll &x, ll &y) { if (b == 0) { x = 1, y = 0; return a; } ll d = exgcd(b, a % b, x, y); ll z = x; x = y; y = z - (a / b) * y; return d; } ll mul(ll a, ll b, ll mod) { ll ans = 0; while (b) { if (b & 1) ans = (ans + a) % mod; a = (a + a) % mod; b >>= 1; } return ans; } ll excrt()//想练excrt于是就写了ex的，其实普通的crt就可以 { ll ans = 0; ll lcm = 1; ll x, y; for (int i = 1; i <= 4; i++) { ll lx = lcm; ll ly = p[i]; ll r = (a[i] - ans % p[i] + p[i]) % p[i]; ll d = exgcd(lx, ly, x, y); ll k = mul(x, (r / d), p[i]); ans += k * lcm; lcm = lcm / d * p[i]; ans = (ans % lcm + lcm) % lcm; } return ans; } ll qpow(ll a, ll b, ll p) { ll ans = 1; while (b) { if (b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans; } ll C(ll n, ll m, ll p) { if (n < m) return 0; return fact[n] * qpow(fact[n - m], p - 2, p) % p * qpow(fact[m], p - 2, p) % p; } ll lucus(ll n, ll m, ll p) { if (n < m) return 0; if (n == 0) return 1; return lucus(n / p, m / p, p) * C(n % p, m % p, p) % p; } void pre(ll p) { fact[0] = 1; for (ll i = 1; i <= p; i++) { fact[i] = fact[i - 1] * i % p; } } int main() { ll q, n; cin >> n >> q; if (q == MOD) { cout << 0 << endl; return 0; } for (ll k = 1; k <= 4; k++) { pre(p[k]); for (ll i = 1; i * i <= n; i++) { if (n % i == 0) { a[k] = (a[k] + lucus(n, i, p[k])) % p[k]; if (i * i != n) a[k] = (a[k] + lucus(n, n / i, p[k])) % p[k]; } } } cout << qpow(q, excrt(), MOD) << endl; return 0; } |