AOJ 0270 モジュロ・クエリ

問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0270
解法
去年のパソコン甲子園の問題。去年の本選のとき解けなかった。
解説にのっているやり方とはちょっと違うやり方でやった。
アルゴリズムは解説のものより log N 倍ぐらい遅いはずだが通った。

二分探索であまりの区切りを見つけて最大のものを見つける。

#include <cstdio>
#include <algorithm>
using namespace std;

int N, Q;
int c[300000];
int main(){
	scanf("%d %d", &N, &Q);
	for(int i = 0; i < N; i++)
		scanf("%d", &c[i]);
	sort(c, c + N);
	for(int i = 0; i < Q; i++){
		int q;
		int ans = -1;
		scanf("%d", &q);
		for(int j = 0; j <= 300000; j += q){
			int idx = distance(c, lower_bound(c, c + N, j)) - 1;
			if(idx < 0) continue;
			if(j - q <= c[idx]){
				ans = max(ans, c[idx] - (j - q));
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}