HUPC 2019 Day1 B: 自身の 2 倍
0 likes70 views
2019/7/14 北海道大学プログラミング合宿 Day1 (北大セット) B 問題
More Related Content
More from HCPC: 北海道大学競技プログラミングサークル (20)
Recently uploaded (11)
HUPC 2019 Day1 B: 自身の 2 倍
- 1. B 問題: 自身の 2 倍 原案: rodea 解説: rodea 問題文: rodea 解答: tsutaj, rsk0315, monkukui, rodea 北大合宿 2019 Day 1
- 2. ? 問題概要 クエリが ? 個与えられ、各クエリにつき 1 個の整数 ? が与えられる。 その整数 ? に対して、 ?2 ≤ ? ≤ ? である ?? の約数のうち、? を除いたものの総積が ? の 2 倍以上になる という 2 つの条件を満たす正の整数 ? の個数を求める。 制約 ?1 ≤ ? ≤ 105 ?2 ≤ ? ≤ 105
- 3. ? 解法 クエリが与えられるたびに計算すると間に合わないため、前処理で 105 まで計算しておく。 ある整数 ? が条件を満たすかを判定するには、2 以上 ? 以下に ? の約数が 2 個以上あるか調べればよい。 これを累積和的にもっておく。 全体の計算量は ?(? ?) で抑えられる。
- 5. ? Writer 解と統計情報 ?tsutaj_sqrt: 28 行 (C++) ?tsutaj_sieve: 63 行 (C++) ?tsutaj_py: 24 行 (Python) ?rsk0315: 29 行 (C++) ?monkukui: 37 行 (C++) ?rodea: 25 行 (C++) Acceptance / Submission ?59.29 % (83 / 140) First Acceptance ?On-site: hupc2019_gorira (15:40) ?On-line: ushitapunichiakun (05:14)