Node.js) 백준 28437번: 막대 만들기

 

https://www.acmicpc.net/problem/28437

28437번: 막대 만들기

 

const input = require('fs')
	.readFileSync('./dev/stdin')
	.toString()
	.trim()
	.split('\n')
	.map((v) => v.split(' ').map(Number));
const N = input[0][0];
const A = input[1];
const Q = input[2][0];
const L = input[3];
let dp = Array(100001).fill(0);
A.forEach((a) => {
	dp[a] = 1;
});

for (let i = 1; i <= 100000; i++) {
	const dest = i;

	const sqrt = Math.floor(Math.sqrt(dest));

	const possible = new Set();

	for (let i = 1; i <= sqrt; i++) {
		if (dest % i == 0) {
			possible.add(i);
			possible.add(dest / i);
		}
	}
	const sum = [...possible].reduce((r, v) => r + dp[v], 0);
	dp[i] = sum;
}
const answer = [];
for (let l = 0; l < Q; l++) {
	const dest = L[l];
	answer.push(dp[dest]);
}
console.log(answer.join(' '));