結果

問題 No.2882 Comeback
ユーザー hiro1729hiro1729
提出日時 2024-09-01 18:01:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,495 bytes
コンパイル時間 367 ms
コンパイル使用メモリ 82,600 KB
実行使用メモリ 83,388 KB
最終ジャッジ日時 2024-09-01 18:01:13
合計ジャッジ時間 4,675 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 46 ms
68,176 KB
testcase_01 AC 46 ms
61,660 KB
testcase_02 AC 47 ms
62,720 KB
testcase_03 AC 46 ms
62,664 KB
testcase_04 AC 47 ms
62,376 KB
testcase_05 TLE -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from math import gcd

# N≦2^64で素数判定
def is_prime(N: int) -> bool:
	if N <= 1:
		return False
	if N == 2:
		return True
	if N & 1 == 0:
		return False
	s = 0
	d = N - 1
	while d & 1 == 0:
		s += 1
		d >>= 1
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		if a % N == 0:
			return True
		x = pow(a, d, N)
		if x != 1:
			t = 0
			while t < s and x < N - 1:
				t += 1
				x = x * x % N
			if t == s:
				return False
	return True

# N以下の最大の素数を返す
def biggest_prime(N: int) -> int:
	while not is_prime(N):
		N -= 1
	return N

# N以上の最小の素数を返す
def smallest_prime(N: int) -> int:
	while not is_prime(N):
		N += 1
	return N

# エラトステネスの篩 [1, N]
def Eratosthenes_Sieve(N: int) -> list:
	if N < 2:
		return []
	p = [True] * (N + 1)
	p[0] = p[1] = False
	for i in range(2, N + 1):
		if i * i > N:
			break
		if p[i]:
			for j in range(2 * i, N + 1, i):
				p[j] = False
	return p

# エラトステネスの区間篩 [A, B]
def Eratosthenes_Sieve2(A: int, B: int) -> list:
	p = [True] * (B - A + 1)
	for i in range(2, B + 1):
		if i * i > B:
			break
		if i < A:
			for j in range((A + i - 1) // i * i, B + 1, i):
				p[j - A] = False
		elif p[i - A]:
			for j in range(2 * i, B + 1, i):
				p[j - A] = False
	return p

# 約数(ソートする)
def divisor(N: int) -> list:
	d = []
	d2 = []
	for i in range(1, N + 1):
		if i * i > N:
			break
		if N % i == 0:
			d.append(i)
			if i * i < N:
				d2.append(N // i)
	return d + d2[::-1]

# 素因数分解
def factorize(N: int) -> list:
	c = 0
	while N & 1 == 0:
		c += 1
		N >>= 1
	ans = [(2, c)]
	while N > 1:
		n = N
		while not is_prime(n):
			m = int(n ** 0.125) + 1
			for c in range(1, n):
				y = 0
				g = 1
				q = 1
				r = 1
				while g == 1:
					x = y
					for _ in range(r >> 1, (3 * r) >> 2):
						y = (y * y + c) % n
					for k in range((3 * r) >> 2, r, m):
						ys = y
						for _ in range(min(m, r - k)):
							y = (y * y + c) % n
							q = q * (x - y) % n
						g = gcd(q, n)
						if g != 1:
							break
					r <<= 1
				if g == n:
					g = 1
					y = ys
					while g == 1:
						y = (y * y + c) % n
						g = gcd(x - y, n)
				if g != n:
					break
			n = g
		c = 0
		while N % n == 0:
			c += 1
			N //= n
		ans.append((n, c))
	ans.sort()
	return ans

for _ in range(int(input())):
	A, B = map(int, input().split())
	ans = 0
	for i in range(A + 1, B + 1):
		ans += len(divisor(i))
	for i in range(B - A):
		ans -= len(divisor(i))
	print(ans)
0