結果

問題 No.97 最大の値を求めるくえり
コンテスト
ユーザー なお
提出日時 2014-12-08 03:35:27
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 347 ms / 5,000 ms
コード長 1,315 bytes
コンパイル時間 1,500 ms
コンパイル使用メモリ 158,440 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-11 18:21:20
合計ジャッジ時間 7,304 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))

const int MOD = 100003;
const int MAX = 100003;
int N, Q;
int inv[MOD];
int res[MOD];
int A[MAX];
bool exist[MOD];

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

void init(int N){
    // ( (inv[i] * i) % MOD == 1) となる配列
    inv[0] = 0; inv[1] = 1;
    for(int i = 2; i < MOD; i++){
        inv[i] = (ll)inv[MOD % i] * (MOD - MOD / i) % MOD;
    }
    REP(i,N) A[i] = xor128() % MOD, exist[A[i]] = true;
    memset(res, -1, sizeof(res));
    res[0] = 0;
}
int solve(int q){
    if(res[q] >= 0) return res[q];
    // 最大がmxになるようなAがあるか調べる
    for(int mx = MOD-1; mx > MOD-1000; mx--){
        if(exist[(ll)mx * inv[q] % MOD]){
            return res[q] = mx;
        }
    }
    // 1000個調べても無かったら総当り
    int mx = 0;
    REP(i,N) mx = max(mx, (int)((ll)q * A[i] % MOD));
    return res[q] = mx;
}

int main(){
    cin >> N >> Q;
    init(N);

    REP(i,Q){
        int q; cin >> q;
        cout << solve(q) << endl;
    }
    return 0;
}
0