#305955 (C++14) No.774 tatyamと素数大富豪

• 問題: No.774 tatyamと素数大富豪
• ユーザー: ldsyb
• 提出日時: 2018-12-22 16:24:55
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 1,264 bytes
• コンパイル時間: 1,836 ms
• コンパイル使用メモリ: 174,012 KB
• 実行使用メモリ: 6,948 KB
• 最終ジャッジ日時: 2024-09-25 10:11:39
• 合計ジャッジ時間: 4,078 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	AC	3 ms; 6,812 KB
testcase_02	AC	1 ms; 6,944 KB
testcase_03	AC	298 ms; 6,940 KB
testcase_04	AC	27 ms; 6,940 KB
testcase_05	WA	-
testcase_06	AC	2 ms; 6,944 KB
testcase_07	AC	2 ms; 6,940 KB
testcase_08	AC	2 ms; 6,944 KB
testcase_09	AC	13 ms; 6,940 KB
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	AC	7 ms; 6,940 KB
testcase_15	WA	-
testcase_16	AC	4 ms; 6,940 KB
testcase_17	WA	-
testcase_18	WA	-

ソースコード

#include <bits/stdc++.h>
using namespace std;

template <typename T>
T gcd(T a, T b)
{
	while (b)
	{
		T tmp = b;
		b = a % b;
		a = tmp;
	}
	return a;
}

template <typename T>
T pow_mod(T a, T n, T mod)
{
	T r = 1;
	for (; n; n >>= 1)
	{
		if (n & 1)
		{
			(r *= a) %= mod;
		}
		(a *= a) %= mod;
	}
	return r;
}

template <typename T>
bool miller_rabin(T n)
{
	if (n < 2)
	{
		return false;
	}
	for (T a = 2; a < min(T(1000), n); a++)
	{
		if (gcd(a, n) != 1)
		{
			continue;
		}
		T m = n - 1;
		if (pow_mod(a, m, n) != 1)
		{
			return false;
		}
		for (m >>= 1; m % 2 == 0; m >>= 1)
		{
			T puni = pow_mod(a, m, n);
			if (puni == n - 1)
			{
				break;
			}
			if (puni != 1)
			{
				return false;
			}
		}
		T puni = pow_mod(a, m, n);
		if ((puni != n - 1) && (puni != 1))
		{
			return false;
		}
	}
	return true;
}

int main()
{
	auto is_prime = [](int64_t n) {
		return miller_rabin(n);
	};
	int n;
	cin >> n;
	vector<int> as(n);
	for (auto &a : as)
	{
		cin >> a;
	}
	sort(as.begin(), as.end());
	int64_t ans = -1;
	do
	{
		string s = ""s;
		for (auto &a : as)
		{
			s += to_string(a);
		}
		int64_t x = stoll(s);
		if (is_prime(x))
		{
			ans = max(ans, x);
		}
	} while (next_permutation(as.begin(), as.end()));
	cout << ans << endl;
	return 0;
}