結果

問題 No.97 最大の値を求めるくえり
ユーザー なおなお
提出日時 2014-12-08 03:35:27
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 363 ms / 5,000 ms
コード長 1,315 bytes
コンパイル時間 1,171 ms
コンパイル使用メモリ 144,912 KB
実行使用メモリ 4,624 KB
最終ジャッジ日時 2023-09-02 11:37:18
合計ジャッジ時間 7,180 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
4,376 KB
testcase_01 AC 4 ms
4,624 KB
testcase_02 AC 194 ms
4,376 KB
testcase_03 AC 161 ms
4,380 KB
testcase_04 AC 363 ms
4,380 KB
testcase_05 AC 363 ms
4,376 KB
testcase_06 AC 356 ms
4,384 KB
testcase_07 AC 339 ms
4,380 KB
testcase_08 AC 309 ms
4,380 KB
testcase_09 AC 261 ms
4,380 KB
testcase_10 AC 222 ms
4,380 KB
testcase_11 AC 204 ms
4,380 KB
testcase_12 AC 190 ms
4,376 KB
testcase_13 AC 192 ms
4,376 KB
testcase_14 AC 181 ms
4,388 KB
testcase_15 AC 175 ms
4,376 KB
testcase_16 AC 170 ms
4,380 KB
testcase_17 AC 176 ms
4,416 KB
testcase_18 AC 173 ms
4,612 KB
権限があれば一括ダウンロードができます

ソースコード

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