結果

問題 No.97 最大の値を求めるくえり
コンテスト
ユーザー 37zigen
提出日時 2020-08-30 23:45:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 443 ms / 5,000 ms
コード長 1,507 bytes
コンパイル時間 843 ms
コンパイル使用メモリ 73,704 KB
最終ジャッジ日時 2025-01-14 02:11:59
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:26:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
   26 | main() {
      | ^~~~

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;

const long long MOD=100003;
long long ind[MOD];

long long pow_mod(long long a,long long n) {
    return n!=0?pow_mod(a*a%MOD,n/2)*(n%2==1?a:1)%MOD:1;
}

unsigned xor128_x = 123456789, xor128_y = 362436069, xor128_z = 521288629, xor128_w = 88675123;
unsigned xor128() {
	unsigned t = xor128_x ^ (xor128_x << 11);
	xor128_x = xor128_y; xor128_y = xor128_z; xor128_z = xor128_w;
	return xor128_w = xor128_w ^ (xor128_w >> 19) ^ (t ^ (t >> 8));
}

vector<int> generateA(int N) {
  vector<int> A(N);
  for(int i = 0; i < N; ++ i)
    A[i] = xor128() % MOD;
  return A;
}

main() {
    int g=2;
    for (int i=0;i<MOD;++i) {
        ind[pow_mod(g,i)]=i;
    }
    
    int N,Q;
    cin>>N>>Q;
    bool ok[MOD];
    auto A=generateA(N);
    int sz=0;
    for (int i=0;i<MOD;++i) ok[i]=false;
    for (long long v:A) {
        if (v!=0) {
            ok[ind[v]]=true;
            ++sz;
        }
    }
    while (Q--) {
        int q;
        cin>>q;
        if (q==0) {
            cout<<0<<endl;
            continue;
        }
        int ind_q=ind[q];
        int ans=0;
        int ord=MOD-1;
        if (N>1000) {
            for (int i=MOD-1;i>=1;--i) {
                if (ok[(ind[i]-ind_q+ord)%ord]) {
                    ans=i;
                    break;
                }
            }
        } else {
            for (long long v:A) {
                ans=max(ans,(int)(v*q%MOD));
            }
        }
        cout<<ans<<endl;
    }
    
}
0