No.97 最大の値を求めるくえり - yukicoder
- N の大小でアルゴリズムを切り替える。って発想がなかなかできない。
class MaxmumValueQuery {
public:
void solve(void) {
int N,Q;
cin>>N>>Q;
vector<int> A(N);
generateA(N,A);
sort(RANGE(A));
vector<bool> exist(Mod, false);
REP(i,N)
exist[A[i]] = true;
REP(_,Q)
{
int q;
cin>>q;
if (N <= 500)
{
ll ans = 0;
REP(i,N)
ans = max(ans, (ll)A[i]*q%Mod);
cout<<ans<<endl;
}
else
{
if (q==0)
{
cout<<0<<endl;
continue;
}
ll inv_q = mod_pow(q, Mod-2);
for (int m = Mod-1; m >= 0; --m)
{
int l = inv_q*m%Mod;
if ( exist[l] )
{
cout<<m<<endl;
break;
}
}
}
}
}
};