#28640 (C++11) No.6 使いものにならないハッシュ

• 問題: No.6 使いものにならないハッシュ
• ユーザー: vain0
• 提出日時: 2015-05-25 00:43:31
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 4 ms / 5,000 ms
• コード長: 1,181 bytes
• コンパイル時間: 542 ms
• コンパイル使用メモリ: 71,760 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-16 16:26:47
• 合計ジャッジ時間: 1,506 ms
• ジャッジサーバーID （参考情報）: judge6 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	4 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	3 ms; 5,376 KB
testcase_07	AC	3 ms; 5,376 KB
testcase_08	AC	2 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	4 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB
testcase_15	AC	3 ms; 5,376 KB
testcase_16	AC	2 ms; 5,376 KB
testcase_17	AC	3 ms; 5,376 KB
testcase_18	AC	4 ms; 5,376 KB
testcase_19	AC	3 ms; 5,376 KB
testcase_20	AC	3 ms; 5,376 KB
testcase_21	AC	2 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	3 ms; 5,376 KB
testcase_27	AC	3 ms; 5,376 KB
testcase_28	AC	3 ms; 5,376 KB
testcase_29	AC	4 ms; 5,376 KB
testcase_30	AC	3 ms; 5,376 KB
testcase_31	AC	3 ms; 5,376 KB

ソースコード

#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
using namespace std;
#define repi(_I, _B, _E) for(int _I = (_B); (_I) < (_E); ++ (_I))
#define rep(_I, _N) for(int _I = 0; (_I) < (_N); ++ (_I))
#define all(_X) (_X).begin(), (_X).end()

int hf(int a) {
	while ( a >= 10 ) {
		int x = 0;
		while ( a > 0 ) {
			x += a % 10;
			a /= 10;
		}
		a = x;
	}
	return a;
}

bool is_prime[200000+1];

int k, n;
void next_prime(int& a) {
	do { ++a; } while (!is_prime[a] && a < n);
	return;
}

int main() {
	cin >> k >> n;
	++n;

	//ふるい
	fill(is_prime, is_prime + n, true);
	is_prime[0] = is_prime[1] = false;
	for ( int i = 2; i * i < n; ++ i) {
		if ( is_prime[i] ) {
			for ( int j = 2; i * j < n; ++j ) {
				is_prime[i * j] = false;
			}
		}
	}

	//しゃくとり
	int s = k - 1; next_prime(s);
	int t = s;
	int maxlen = 0, p = 0;
	int len = 0;
	bool hs[10] {};
	while (t < n) {
		while (t < n && !hs[hf(t)]) {
			hs[hf(t)] = true;
			len++;
			next_prime(t);
		}

		if ( maxlen <= len ) {
			maxlen = len;
			p = s;
		}

		len--;
		hs[hf(s)] = false;
		next_prime(s);
	}
	cout << p << endl;
	return 0;
}