ABC084-D.2017-like Number
概要
「N も (N + 1) / 2 も素数」を満たす奇数 N
上記を満たす値を2017に似た数とし、
与えられた区間にいくつ存在するかを問われている。
考え
1..105(制約 r <= 105)の区間で2017に似た数の総数を保持する累積和を作って、
与えられた、l , r (r+1) の区間で似た数が存在するかを出力すればいけると考えた。
素数か否か
i が素数か否かを表す配列を用意
const rMax = 10**5;
const flag = (): number[] => {
const list = Array.from({ length: rMax },() => 1);
list[0] = 0, list[1] = 0;
for (let i = 2; i <= rMax; i++) {
if (list[i]) {
for (let j = i*2; j <= rMax; j+=i) {
list[j] = 0;
}
}
}
return list;
}
2017に似た数か否か
素数判定の配列に対して、
問いの条件を満たすか否かを表す配列を用意
const flagList = flag();
const prefix = Array.from({ length: rMax }, () => 0);
for (let i = 0; i < rMax; i++) {
if (flagList[i] && flagList[Number((i+1)/2)]) {
prefix[i] = 1;
}
}
累積和
2017に似た数が i までに幾つ存在するかを表す配列
const a = Array.from({ length: rMax+1 }, () => 0);
for (let i = 0; i < rMax; i++) {
a[i+1] = a[i] + prefix[i];
}
提出コード
import fs from 'fs';
const input = fs.readFileSync('/dev/stdin', 'utf-8').trim();
const main = (): void => {
const rMax = 10**5;
const flag = (): number[] => {
const list = Array.from({ length: rMax },() => 1);
list[0] = 0, list[1] = 0;
for (let i = 2; i <= rMax; i++) {
if (list[i]) {
for (let j = i*2; j <= rMax; j+=i) {
list[j] = 0;
}
}
}
return list;
}
const flagList = flag();
const prefix = Array.from({ length: rMax }, () => 0);
for (let i = 0; i < rMax; i++) {
if (flagList[i] && flagList[Number((i+1)/2)]) {
prefix[i] = 1;
}
}
const a = Array.from({ length: rMax+1 }, () => 0);
for (let i = 0; i < rMax; i++) {
a[i+1] = a[i] + prefix[i];
}
const lines = input.split(/\s+/).map(Number);
const Q = lines[0];
for (let i = 0; i < Q; i++) {
const right = lines[i*2+1];
const left = lines[i*2+2];
console.log(a[left+1]-a[right])
}
}
main();