コンテンツにスキップ

SamCoding Round 11 (Div. 1) A - Lamps and Switches

サイト
SamCoding
コンテスト
SamCoding Round 11 (Div. 1)
問題
A - Lamps and Switches(常設版)

11 から 101810^{18} までの番号が付いたランプがあり、最初はすべて消えています。各 ii について、番号が ii の倍数であるランプの点灯状態を一度ずつ反転します。

すべての操作の後、番号が ll 以上 rr 以下のランプのうち、点灯しているものの個数を求める問題です。質問は最大 10510^5 個あり、1≤l≤r≤10181 \le l \le r \le 10^{18} です。

番号 xx のランプは、xx の約数に対応するスイッチを押したときに反転します。最初は消えているので、約数の個数が奇数なら点灯し、偶数なら消えています。

約数は通常、dd と x/dx/d の組になります。ただし、xx が平方数のときだけ、d=x/d=xd=x/d=\sqrt{x} となる約数が 11 つあります。よって、約数の個数が奇数になるのは平方数のときだけです。

つまり、求めるものは区間 [l,r][l,r] に含まれる平方数の個数です。tt 以下の正の平方数は 12,22,…,⌊t⌋21^2,2^2,\dots,\lfloor\sqrt{t}\rfloor^2 の ⌊t⌋\lfloor\sqrt{t}\rfloor 個なので、答えは

⌊r⌋−⌊l−1⌋\lfloor\sqrt{r}\rfloor-\lfloor\sqrt{l-1}\rfloor

となります。

Python の math.isqrt(t) は、⌊t⌋\lfloor\sqrt{t}\rfloor を整数のまま正確に求めます。浮動小数点数を経由しないので、101810^{18} 付近の値も丸め誤差を気にせず扱えます。コードの q(t) が、tt 以下の点灯しているランプの個数に対応します。

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))