結果

問題 No.97 最大の値を求めるくえり
コンテスト
ユーザー te-sh
提出日時 2017-04-21 12:18:43
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 390 ms / 5,000 ms
コード長 1,280 bytes
コンパイル時間 906 ms
コンパイル使用メモリ 105,216 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-12 18:47:58
合計ジャッジ時間 4,819 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.algorithm, std.conv, std.range, std.stdio, std.string;

void main()
{
  auto rd = readln.split.to!(int[]), n = rd[0], qn = rd[1];
  auto ai = generateA(n);

  if (n < 3000) {
    calc1(ai, qn);
  } else {
    calc2(ai, qn);
  }
}

void calc1(long[] ai, int qn)
{
  foreach (_; 0..qn) {
    auto q = readln.chomp.to!long;
    writeln(ai.map!(a => a * q % p).maxElement);
  }
}

void calc2(long[] ai, int qn)
{
  auto bi = new bool[](p);
  foreach (a; ai) bi[a] = true;

  foreach (_; 0..qn) {
    auto q = readln.chomp.to!long;

    if (q == 0) {
      writeln(0);
    } else {
      long qi, d;
      exEuclid(q, p, qi, d);
      foreach_reverse (m; 0..p) {
        auto i = ((m * qi) % p + p) % p;
        if (bi[i]) {
          writeln(m);
          break;
        }
      }
    }
  }
}

const p = 100003;

uint x = 123456789, y = 362436069, z = 521288629, w = 88675123;
uint xor128()
{
  uint t = x ^ (x << 11);
  x = y; y = z; z = w;
  return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}

long[] generateA(int n)
{
  auto ai = new long[](n);
  foreach (i, ref a; ai)
    a = xor128 % p;
  return ai;
}

pure T exEuclid(T)(T a, T b, ref T x, ref T y)
{
  auto g = a;
  x = 1;
  y = 0;
  if (b != 0) {
    g = exEuclid(b, a % b, y, x);
    y -= a / b * x;
  }
  return g;
}
0