結果

問題 No.12 限定された素数
コンテスト
ユーザー Onju
提出日時 2015-02-10 04:06:57
言語 C++11(old_compat)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -include bits/stdc++.h -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 34 ms / 5,000 ms
コード長 1,483 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,190 ms
コンパイル使用メモリ 170,652 KB
実行使用メモリ 13,944 KB
最終ジャッジ日時 2026-03-08 16:01:26
合計ジャッジ時間 2,946 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
#include <vector>
#define N_MAX 10
#define L_MAX 5000000
using namespace std;

typedef struct
{
	int value;
	int usednum;
}Prime;

int bitNum(int n)
{
	int bit = 0;
	while (n)
	{
		bit |= 1 << (n % 10);
		n /= 10;
	}
	return bit;
}

vector<Prime>* getPrime(int N)
{
	auto list = new bool[N + 1];
	auto prime = new vector<Prime>();
	int sn = (int)sqrt(N);

	list[0] = list[1] = false;
	for (int i = 2; i <= N; ++i)
		list[i] = true;

	for (int i = 2; i <= sn; ++i)
	{
		if (list[i])
		{
			int jmax = N / i;
			for (int j = i; j <= jmax; ++j)
				list[i*j] = false;
		}
	}

	for (int i = 2; i <= N; ++i)
	{
		if (list[i])
		{
			prime->push_back(Prime{ i, bitNum(i) });
		}
	}

	delete[] list;

	return prime;
}

int main()
{
	int N, A[N_MAX], AA = 0, revAA, LK = -1;
	auto prime = getPrime(L_MAX);
	int num;
	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		cin >> A[i];
		AA |= 1 << A[i];
	}
	revAA = ~AA;

	//全使用の自明パターン
	if (N == 10)
	{
		cout << L_MAX - 1 << endl;
		return 0;
	}

	int used = 0, start = 1;
	for (auto it = prime->begin(); it != prime->end(); ++it)
	{
		if ((*it).usednum & revAA)
		{
			if (used == AA)
			{
				if ((*it).value - start - 1 > LK)
					LK = (*it).value - start - 1;
			}

			start = (*it).value + 1;
			used = 0;
		}
		else
		{
			used |= (*it).usednum;
		}
	}

	//端処理
	if ((used == AA) && (L_MAX - start > LK))
		LK = L_MAX - start;

	cout << LK << endl;

	delete prime;

	return 0;
}
0