結果

問題 No.6 使いものにならないハッシュ
ユーザー 古寺いろは古寺いろは
提出日時 2015-04-16 01:33:51
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 4 ms
5,376 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 4 ms
5,376 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 3 ms
5,376 KB
testcase_13 AC 3 ms
5,376 KB
testcase_14 AC 3 ms
5,376 KB
testcase_15 AC 3 ms
5,376 KB
testcase_16 AC 3 ms
5,376 KB
testcase_17 AC 4 ms
5,376 KB
testcase_18 AC 3 ms
5,376 KB
testcase_19 AC 3 ms
5,376 KB
testcase_20 AC 4 ms
5,376 KB
testcase_21 AC 3 ms
5,376 KB
testcase_22 AC 4 ms
5,376 KB
testcase_23 AC 3 ms
5,376 KB
testcase_24 AC 3 ms
5,376 KB
testcase_25 AC 3 ms
5,376 KB
testcase_26 AC 4 ms
5,376 KB
testcase_27 AC 3 ms
5,376 KB
testcase_28 AC 3 ms
5,376 KB
testcase_29 AC 3 ms
5,376 KB
testcase_30 AC 4 ms
5,376 KB
testcase_31 AC 3 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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