結果
問題 | No.984 Inversion |
ユーザー |
![]() |
提出日時 | 2020-02-11 15:18:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 36 ms / 2,000 ms |
コード長 | 2,241 bytes |
コンパイル時間 | 768 ms |
コンパイル使用メモリ | 86,596 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-01 07:52:56 |
合計ジャッジ時間 | 2,012 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 24 |
ソースコード
#include <stdio.h>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <algorithm>#include <vector>#include <set>#include <map>#include <queue>#include <stack>#include <list>#include <iterator>#include <assert.h>#pragma warning(disable:4996)typedef long long ll;#define MIN(a, b) ((a)>(b)? (b): (a))#define MAX(a, b) ((a)<(b)? (b): (a))#define LINF 9223300000000000000#define INF 2140000000const long long MOD = 1000000007;//const long long MOD = 998244353;using namespace std;// a^blong long modpow(long long a, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}// a^-1long long modinv(long long a, long long m) {long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}// a^x ≡ b (mod. m) となる最小の正の整数 x を求めるlong long modlog(long long a, long long b, int m) {a %= m, b %= m;// calc sqrt{M}long long lo = -1, hi = m;while (hi - lo > 1) {long long mid = (lo + hi) / 2;if (mid * mid >= m) hi = mid;else lo = mid;}long long sqrtM = hi;// {a^0, a^1, a^2, ..., a^sqrt(m)}map<long long, long long> apow;long long amari = 1;for (long long r = 0; r < sqrtM; ++r) {if (!apow.count(amari)) apow[amari] = r;(amari *= a) %= m;}// check each A^plong long A = modpow(modinv(a, m), sqrtM, m);amari = b;for (long long q = 0; q < sqrtM; ++q) {if (apow.count(amari)) {long long res = q * sqrtM + apow[amari];if (res > 0) return res;}(amari *= A) %= m;}// no solutionsreturn -1;}void solve(){int p,n;scanf("%d%d", &p, &n);ll a=modlog(n,1,p);ll b=(p-1)/a;ll ans=((b%2)*((a-1)%2));printf("%lld\n", ans);return;}int main(int argc, char* argv[]){#if 1solve();#elseint T; scanf("%d", &T);while(T--) {solve();}#endifreturn 0;}