AtCoder が提供しているABC（AtCoder Beginner Contest）096 D問題をC++で解いてみました。ABC096は、2018年5月5日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Five, Five Everywhere（Difficulty : 1226）
問題の詳細は、リンク先をご覧ください。
ABC096 D問題 Five, Five Everywhere
興味深い整数の問題を紹介します。AtCoder Problems による Difficulty は 1226 でした。
解答案
問題の本質は以下です。
55555以下の素数から55個を選び、その中の任意の5個の和が合成数となるような組み合わせは存在しますか？
55555以下の素数表は簡単に作成できます。その中から5個を選び、その和が合成数になる例として、入力例1の「3、5、7、11、31」があります。しかし、この方法を拡張するのは難しいです。
視点を変えると、この問題は「$5N+1$ となる素数を55個選ぶ」ことで解決できます。$5N+1$ となる素数を5個選ぶと、その和は5の倍数となり、合成数になります。
C++ プログラム例（ABC096D）
エラトステネスの篩で、55555以下の素数表を作成します（8ー31、38行目）。この素数表から、5で割って1余る素数を配列 result に格納します。
- 55555以下の素数は、5637個ありました。
- その中で5で割って1余る素数は、1408個ありました。
最後に、配列 result の先頭から $n$ 個の素数を出力します。以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
#define N 55555
bool is_prime_table[N + 1];
vector<int> primes;
void generate_primes(int n)
{
is_prime_table[0] = false;
is_prime_table[1] = false;
for (int i = 2; i <= n; ++i) {
is_prime_table[i] = true;
}
for (int i = 2; i * i <= n; ++i) {
if (is_prime_table[i]) {
for (int j = i + i; j <= n; j += i) {
is_prime_table[j] = false;
}
}
}
for (int i = 2; i <= n; ++i) {
if (is_prime_table[i]) {
primes.push_back(i);
}
}
return;
}
int main()
{
int n;
cin >> n;
generate_primes(55555);
vector<int> result;
for (int i = 0; i < (int)primes.size(); ++i) {
if (primes[i] % 5 == 1) {
result.push_back(primes[i]);
}
}
for (int i = 0; i < n; ++i) {
cout << result[i] << " \n"[i == n - 1];
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
最後に
過去のABCの問題ですが、学びが多かったため記事にしました。高校数学の整数問題でも、「合同式を用いる」と上手く解ける場合があったことを思い出しました。
引き続き ABC の問題を紹介していきます。
