結果

問題 No.6 使いものにならないハッシュ
コンテスト
ユーザー 古寺いろは
提出日時 2015-04-16 01:33:51
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 934 bytes
コンパイル時間 2,372 ms
コンパイル使用メモリ 161,380 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-16 16:24:50
合計ジャッジ時間 2,761 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define MAX 200005

bool pdp[MAX];
vector<int> makeprime(){
	vector<int> ret;
	for (int i = 2; i < MAX; i++)
	{
		if (pdp[i]) continue;
		ret.push_back(i);
		for (int j = i + i; j < MAX; j += i)
		{
			pdp[j] = true;
		}
	}
	return ret;
}

int makehash(int a){
	int ret = 0;
	while (a > 0){
		ret += a % 10;
		a /= 10;
	}
	if (ret >= 10) return makehash(ret);
	return ret;
}

int main() {
	auto prime = makeprime();
	int K, N;
	cin >> K >> N;
	int j = 0;
	while (prime[j] < K) j++;

	vector<int> dp(1000, 0);
	int ans = 0;
	int anslen = 0;
	for (int i = 0; i < prime.size(); i++)
	{
		if (prime[i] < K) continue;
		if (prime[i] > N) break;
		int ihash = makehash(prime[i]);
		dp[ihash]++;
		while (dp[ihash] > 1){
			int jhash = makehash(prime[j++]);
			dp[jhash]--;
		}
		if (i - j + 1 >= anslen){
			ans = prime[j];
			anslen = i - j + 1;
		}
	}
	cout << ans << endl;
	cin >> ans;
}
0