結果

問題 No.1498 Factorization from -1 to 1
ユーザー hos.lyric
提出日時 2021-05-04 00:10:04
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 320 ms / 3,000 ms
コード長 4,722 bytes
コンパイル時間 956 ms
コンパイル使用メモリ 125,820 KB
実行使用メモリ 13,100 KB
最終ジャッジ日時 2024-06-22 11:15:59
合計ジャッジ時間 6,139 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }


// xorshift
uint xrand() {
  static uint x = 314159265, y = 358979323, z = 846264338, w = 327950288;
  uint t = x ^ x << 11; x = y; y = z; z = w; return w = w ^ w >> 19 ^ t ^ t >> 8;
}

// a^-1 (mod m)
long modInv(long a, long m)
in {
  assert(m > 0, "modInv: m > 0 must hold");
}
do {
  long b = m, x = 1, y = 0, t;
  for (; ; ) {
    t = a / b; a -= t * b;
    if (a == 0) {
      assert(b == 1 || b == -1, "modInv: gcd(a, m) != 1");
      if (b == -1) y = -y;
      return (y < 0) ? (y + m) : y;
    }
    x -= t * y;
    t = b / a; b -= t * a;
    if (b == 0) {
      assert(a == 1 || a == -1, "modInv: gcd(a, m) != 1");
      if (a == -1) x = -x;
      return (x < 0) ? (x + m) : x;
    }
    y -= t * x;
  }
}

// (a / 2) mod m
long div2(long a, long m)
in {
  assert(1 <= m && m < 1L << 62, "div2: 1 <= m < 2^62 must hold");
  assert(m % 2 != 0, "div2: m must not be divisible by 2");
  assert(0 <= a && a < m, "div2: 0 <= a < m must hold");
}
do {
  return (a + (a % 2) * m) / 2;
}

// (a / 3) mod m
long div3(long a, long m)
in {
  assert(1 <= m && m < 1L << 61, "div3: 1 <= m < 2^61 must hold");
  assert(m % 3 != 0, "div3: m must not be divisible by 3");
  assert(0 <= a && a < m, "div3: 0 <= a < m must hold");
}
do {
  return (a + (((3 - a % 3) * (m % 3)) % 3) * m) / 3;
}

// Jacobi symbol (a/m)
int jacobi(long a, long m)
in {
  assert(m > 0, "jacobi: m > 0 must hold");
  assert(m & 1, "jacobi: m must be odd");
}
do {
  import core.bitop : bsf;
  import std.algorithm.mutation : swap;
  int s = 1;
  if (a < 0) a = a % m + m;
  for (; m > 1; ) {
    a %= m;
    if (a == 0) return 0;
    const r = bsf(a);
    if ((r & 1) && ((m + 2) & 4)) s = -s;
    a >>= r;
    if (a & m & 2) s = -s;
    swap(a, m);
  }
  return s;
}

// sqrt(a) (mod p)
//   p: be prime
//   (b + sqrt(b^2 - a))^((p+1)/2) in F_p(sqrt(b^2 - a))
long[] modSqrt(long a, long p)
in {
  assert(p < 1L << 31, "modSqrt: p < 2^31 must hold");
  assert(-p * p <= a && a <= p * p, "modSqrt: -p^2 <= a <= p^2 must hold");
}
do {
  if (p == 2) return [a & 1];
  const j = jacobi(a, p);
  if (j == 0) return [0];
  if (j == -1) return [];
  long b, d;
  for (; ; ) {
    b = xrand() % p;
    d = (b * b - a) % p;
    if (d < 0) d += p;
    if (jacobi(d, p) == -1) break;
  }
  long[2] mul(in long[2] x, in long[2] y) {
    return [(x[0] * y[0] + d * ((x[1] * y[1]) % p)) % p,
            (x[0] * y[1] + x[1] * y[0]) % p];
  }
  long[2] f = [b, 1], g = [1, 0];
  for (long e = (p + 1) >> 1; e; e >>= 1) {
    if (e & 1) g = mul(g, f);
    f = mul(f, f);
  }
  assert(g[1] == 0);
  return (g[0] < p - g[0]) ? [g[0], p - g[0]] : [p - g[0], g[0]];
}


enum N = 10^^5 + 10;

void main() {
  auto lpf = iota(N).array;
  foreach (p; 2 .. N) {
    if (lpf[p] == p) {
      for (int n = 2 * p; n < N; n += p) {
        chmin(lpf[n], p);
      }
    }
  }
  auto pss = new int[][N];
  foreach (p; 2 .. N) {
    if (lpf[p] == p) {
      foreach (x; modSqrt(-1, p)) {
        for (long n = x; n < N; n += p) {
          pss[cast(int)(n)] ~= p;
        }
      }
    }
  }
  
  try {
    for (; ; ) {
      const Q = readInt();
      foreach (q; 0 .. Q) {
        const n = readInt();
        
        long m = 1L * n * n + 1;
        long[] ans;
        foreach (p; pss[n]) {
          for (; m % p == 0; m /= p) {
            ans ~= p;
          }
        }
        if (m > 1) {
          ans ~= m;
        }
        
        foreach (index, p; ans) {
          if (index > 0) write(" ");
          write(p);
        }
        writeln;
      }
    }
  } catch (EOFException e) {
  }
}
0