SamCoding Round 11 (Div. 1) A - Lamps and Switches
- サイト
- SamCoding
- コンテスト
- SamCoding Round 11 (Div. 1)
- 問題
- A - Lamps and Switches(常設版)
から までの番号が付いたランプがあり、最初はすべて消えています。各 について、番号が の倍数であるランプの点灯状態を一度ずつ反転します。
すべての操作の後、番号が 以上 以下のランプのうち、点灯しているものの個数を求める問題です。質問は最大 個あり、 です。
番号 のランプは、 の約数に対応するスイッチを押したときに反転します。最初は消えているので、約数の個数が奇数なら点灯し、偶数なら消えています。
約数は通常、 と の組になります。ただし、 が平方数のときだけ、 となる約数が つあります。よって、約数の個数が奇数になるのは平方数のときだけです。
つまり、求めるものは区間 に含まれる平方数の個数です。 以下の正の平方数は の 個なので、答えは
となります。
Python の math.isqrt(t) は、 を整数のまま正確に求めます。浮動小数点数を経由しないので、 付近の値も丸め誤差を気にせず扱えます。コードの q(t) が、 以下の点灯しているランプの個数に対応します。
Python
import math
def q(t): return math.isqrt(t)
for _ in range(int(input())): l, r = map(int, input().split()) print(q(r) - q(l - 1))