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

• 問題: No.6 使いものにならないハッシュ
• ユーザー: kenken714
• 提出日時: 2019-04-17 20:28:44
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 88 ms / 5,000 ms
• コード長: 1,328 bytes
• コンパイル時間: 707 ms
• コンパイル使用メモリ: 92,160 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-16 16:49:20
• 合計ジャッジ時間: 2,775 ms
• ジャッジサーバーID （参考情報）: judge6 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	88 ms; 5,376 KB
testcase_03	AC	9 ms; 5,376 KB
testcase_04	AC	15 ms; 5,376 KB
testcase_05	AC	17 ms; 5,376 KB
testcase_06	AC	44 ms; 5,376 KB
testcase_07	AC	25 ms; 5,376 KB
testcase_08	AC	39 ms; 5,376 KB
testcase_09	AC	16 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	10 ms; 5,376 KB
testcase_12	AC	51 ms; 5,376 KB
testcase_13	AC	10 ms; 5,376 KB
testcase_14	AC	16 ms; 5,376 KB
testcase_15	AC	41 ms; 5,376 KB
testcase_16	AC	31 ms; 5,376 KB
testcase_17	AC	66 ms; 5,376 KB
testcase_18	AC	83 ms; 5,376 KB
testcase_19	AC	64 ms; 5,376 KB
testcase_20	AC	53 ms; 5,376 KB
testcase_21	AC	6 ms; 5,376 KB
testcase_22	AC	59 ms; 5,376 KB
testcase_23	AC	51 ms; 5,376 KB
testcase_24	AC	55 ms; 5,376 KB
testcase_25	AC	29 ms; 5,376 KB
testcase_26	AC	70 ms; 5,376 KB
testcase_27	AC	52 ms; 5,376 KB
testcase_28	AC	28 ms; 5,376 KB
testcase_29	AC	73 ms; 5,376 KB
testcase_30	AC	62 ms; 5,376 KB
testcase_31	AC	57 ms; 5,376 KB

ソースコード

#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>

using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>


ll a, b, ma = 0, ans;

vector<ll> prime, h;

bool IsPrime(ll n) {
	if (n <= 1)return false;
	for (ll i = 2; i <= sqrt(n); i++)
	{
		if (n % i == 0)return false;
	}
	return true;
}

int hs(ll a) {
	ll res = a;
	while (res > 9) {
		ll next = 0;
		while (res > 0) {
			next += res % 10;
			res /= 10;
		}
		res = next;
	}
	return res;
}

int main() {
	cin >> a >> b;
	FOR(i, a, b + 1)if (IsPrime(i))prime.push_back(i);
	REP(i, prime.size())h.push_back(hs(prime[i]));
	REPR(i, h.size() - 1) {
		ll now = 0;
		set<ll> se;
		FOR(j, i, h.size()) {
			if (se.find(h[j]) != se.end())break;
			else {
				se.insert(h[j]);
				now++;
			}
		}
		if (ma < now) {
			ma = now;
			ans = prime[i];
		}
	}
	
	
	cout << ans << endl;
}