結果

問題 No.181 A↑↑N mod M
コンテスト
ユーザー nonamae
提出日時 2021-10-04 10:06:02
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 6,556 bytes
コンパイル時間 673 ms
コンパイル使用メモリ 43,976 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-22 09:27:25
合計ジャッジ時間 2,015 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <assert.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/* signed integer */
typedef   int8_t      i8;
typedef   int16_t     i16;
typedef   int32_t     i32;
typedef   int64_t     i64;
typedef __int128_t    i128;

/* unsigned integer */
typedef   uint8_t     u8;
typedef   uint16_t    u16;
typedef   uint32_t    u32;
typedef   uint64_t    u64;
typedef __uint128_t   u128;

/* floating point number */
typedef   float       f32;
typedef   double      f64;
typedef   long double f80;

typedef   int         FastInt;

/* io */
static inline FastInt read_int(void) {
  FastInt c, x = 0, f = 1;
  while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f;
  while (47 < c && c < 58) {
    x = x * 10 + c - 48;
    c = getchar_unlocked();
  }
  return f * x;
}
static inline i64 in(void) {
  i64 c, x = 0, f = 1;
  while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f;
  while (47 < c && c < 58) {
    x = x * 10 + c - 48;
    c = getchar_unlocked();
  }
  return f * x;
}
static inline u64 inu(void) {
  u64 c, x = 0;
  while (c = getchar_unlocked(), c < 48 || c > 57);
  while (47 < c && c < 58) {
    x = x * 10 + c - 48;
    c = getchar_unlocked();
  }
  return x;
}
static inline void write_int(FastInt x) {
  if (x < 0) {
    putchar_unlocked('-');
    x = -x;
  }
  if (x >= 10) write_int(x / 10);
  putchar_unlocked(x - x / 10 * 10 + 48);
}
static inline void out(i64 x) {
  if (x < 0) {
    putchar_unlocked('-');
    x = -x;
  }
  if (x >= 10) out(x / 10);
  putchar_unlocked(x - x / 10 * 10 + 48);
}
static inline void outu(u64 x) {
  if (x >= 10) outu(x / 10);
  putchar_unlocked(x - x / 10 * 10 + 48);
}
static inline void NL(void) { putchar_unlocked('\n'); }
static inline void SP(void) { putchar_unlocked(' '); }

/* MACROS */
#define POPCNT(a) __builtin_popcountll((a))
#define CTZ(a) __builtin_ctzll((a))
#define CLZ(a) __builtin_clzll((a))
#define LSBit(a) ((a)&(-(a)))
#define CLSBit(a) ((a)&((a)-(1)))
#define HAS_SINGLE_BIT(a) (POPCNT((a))==1)
#define BIT_CEIL(a) ((!(a))?(1):((POPCNT(a))==(1)?((1ull)<<((63)-CLZ((a)))):((1ull)<<((64)-CLZ(a)))))
#define BIT_FLOOR(a) ((!(a))?(0):((1ull)<<((63)-CLZ((a)))))
#define BIT_WIDTH(a) ((a)?((64)-CLZ((a))):(0))
#define _ROTL(x, s) (((x)<<((s)%(64)))|(((x)>>((64)-((s)%(64))))))
#define _ROTR(x, s) (((x)>>((s)%(64)))|(((x)<<((64)-((s)%(64))))))
#define ROTL(x, s) (((s)==(0))?(0):(((s)<(0))?(_ROTR((x),-(s))):(_ROTL((x),(s)))))
#define ROTR(x, s) (((s)==(0))?(0):(((s)<(0))?(_ROTL((x),-(s))):(_ROTR((x),(s)))))
#define SWAP(a, b) (((a)^=(b)),((b)^=(a)),((a)^=(b)))
#define MAX(a, b) ((a)>(b)?(a):(b))
#define MIN(a, b) ((a)<(b)?(a):(b))


i64 _gcd_(i64 a, i64 b) {
  // assert(a >= 0 && b >= 0);
  if (!a || !b) return a | b;
  FastInt shift = CTZ(a | b);
  a >>= CTZ(a);
  do {
    b >>= CTZ(b);
    if (a > b) SWAP(a, b);
    b -= a;
  } while (b);
  return a << shift;
}
i64 _lcm_(i64 a, i64 b) {
  // assert(a >= 0 && b >= 0);
  return a / _gcd_(a, b) * b;
}


u64 _inv(u64 mod) {
  FastInt i;
  u64 u = 1, v = 0, x = 1ULL << 63;
  for (i = 0; i < 64; i++) {
    if (u & 1) u = (u + mod) >> 1, v = (v >> 1) + x;
    else u >>= 1, v >>= 1;
  }
  return -v;
}
u64 _r2(u64 mod) {
  return (u128)(i128)-1 % mod + 1;
}
u64 _one(u64 mod) {
  return -1ULL % mod + 1;
}
u64 _MR(u128 x, u64 inv, u64 mod) {
    i64 z = (x >> 64) - ((((u64)x * inv) * (u128)mod) >> 64);
    return z < 0 ? z + mod : (u64)z;
}
u64 to_montgomery_form(u64 a, u64 r2, u64 inv, u64 mod) {
  return _MR((u128)a * r2, inv, mod);
}
u64 from_montgomery_form(u64 a, u64 inv, u64 mod) {
  return _MR((u128)a, inv, mod);
}
u64 mulmod_MR(u64 x, u64 y, u64 r2, u64 inv, u64 mod) {
  return _MR((u128)r2 * _MR((u128)x * y, inv, mod), inv, mod);
}
u64 powmod_MR(u64 a, u64 n, u64 r2, u64 inv, u64 mod) {
  u64 res = _one(mod);
  u64 A = to_montgomery_form(a, r2, inv, mod);
  while (n > 0) {
    if (n & 1) res = _MR((u128)res * A, inv, mod);
    A = _MR((u128)A * A, inv, mod);
    n >>= 1;
  }
  return from_montgomery_form(res, inv, mod);
}
bool is_prime(u64 n) {
  if (n <= 3) return n == 2 || n == 3;
  if (!(n & 1)) return false;
  u64 r2 = _r2(n);
  u64 inv = _inv(n);
  u64 s = CTZ(n - 1);
  u64 d = (n - 1) >> s;
  if (n < (1ull << 30)) {
    u64 as[] = {2,7,61};
    for (FastInt i = 0; i < 3; i++) {
      if (_MR(as[i], inv, n) == 0) return true;
      u64 res = powmod_MR(as[i], d, r2, inv, n);
      if (res == 1) continue;
      bool ok = true;
      for (u64 r = 0; r < s; r++) {
        if (res == n - 1) {
          ok = false;
          break;
        }
        res = mulmod_MR(res, res, r2, inv, n);
      }
      if (ok) return false;
    }
    return true;
  } else {
    u64 as[] = {2,325,9375,28178,450775,9780504,1795265022};
    for (FastInt i = 0; i < 7; i++) {
      if (_MR(as[i], inv, n) == 0) return true;
      u64 res = powmod_MR(as[i], d, r2, inv, n);
      if (res == 1) continue;
      bool ok = true;
      for (u64 r = 0; r < s; r++) {
        if (res == n - 1) {
          ok = false;
          break;
        }
        res = mulmod_MR(res, res, r2, inv, n);
      }
      if (ok) return false;
    }
    return true;
  }
}

FastInt totient(FastInt n) {
  if (is_prime(n)) return n - 1;
  else {
    FastInt ret = n;
    for (FastInt a = 2; a * a <= n; a++) {
      if (n % a == 0) {
        while (n % a == 0) n /= a;
        ret -= ret / a;
      }
    }
    if (n > 1) ret -= ret / n;
    return ret;
  }
}
FastInt powmod(FastInt a, FastInt n, FastInt mod) {
  bool state = false;
  if (n >= totient(mod)) state = true;
  FastInt r = 1;
  while(n) {
    if (n & 1) {
      if ((1LL * r * a) > (u64)mod) state = true;
      r = (1LL * r * a) % mod;
    }
    if (1LL * a * a > (u64)mod) state = true;
    a = (1LL * a * a) % mod;
    n >>= 1;
  }
  if (state) return r + mod;
  else return r;
}
FastInt tetration_sub(FastInt a, FastInt b, FastInt mod) {
  if (a == 0) return ~b & 1;
  if (a == 1 || mod == 1) return 1;
  if (b == 1) {
    if (a >= mod) return a % mod + mod;
    else return a;
  }
  FastInt x = tetration_sub(a, b - 1, totient(mod));
  FastInt ret = powmod(a, x, mod); 
  return ret;
}
FastInt tetration(FastInt a, FastInt b, FastInt mod) {
  FastInt ret;
  if (b == 0) ret = (mod == 1) ? 0 : 1;
  else ret = tetration_sub(a, b, mod) % mod;
  return ret;
}

void Main(void) {
  FastInt A = read_int();
  FastInt B = read_int();
  FastInt M = read_int();
  FastInt ans = tetration(A, B, M);
  out(ans);
  NL();
}

int main(void) {
  Main();
  return 0;
}
0