結果

問題 No.2645 Sum of Divisors?
コンテスト
ユーザー shobonvip
提出日時 2024-02-11 17:13:51
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 4,656 bytes
コンパイル時間 175 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 97,196 KB
最終ジャッジ日時 2024-09-28 17:36:54
合計ジャッジ時間 6,791 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample TLE * 1 -- * 2
other -- * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

class MyFloat:
	def __init__(self, N: int, T: int) -> None:
		self.lb = N * 10 ** T
		self.ub = N * 10 ** T
		self.T = T
		
	def __add__(self, other: "MyFloat") -> "MyFloat":
		assert self.T == other.T
		ret = MyFloat(0, self.T)
		ret.lb = self.lb + other.lb
		ret.ub = self.ub + other.ub
		return ret
	
	def __neg__(self):
		ret = MyFloat(0, self.T)
		ret.lb, ret.ub = - self.ub, - self.lb
		return ret

	def __sub__(self, other: "MyFloat") -> "MyFloat":
		assert self.T == other.T
		return self + (- other)

	def __mul__(self, other: "MyFloat") -> "MyFloat":
		a = [self.lb * other.lb, self.lb * other.ub, self.ub * other.lb, self.ub * other.ub]
		ret = MyFloat(0, self.T)
		ret.lb = min(a) // (10 ** self.T)
		ret.ub = (max(a) + (10 ** self.T) - 1) // (10 ** self.T)
		return ret
		
	def __truediv__(self, other: "MyFloat") -> "MyFloat":
		assert other.lb != 0
		assert other.lb * other.ub > 0
		ret = MyFloat(0, self.T)
		ret.lb = self.lb
		ret.ub = self.ub
		if other.ub > 0:
			ret.lb = ret.lb * 10 ** self.T // other.ub
			ret.ub = (ret.ub * 10 ** self.T + other.lb - 1) // other.lb
		else:
			tar = -other
			ret.lb = ret.lb * 10 ** self.T // tar.ub
			ret.ub = (ret.ub * 10 ** self.T + tar.lb - 1) // tar.lb
			ret = -ret
		return ret

	def __str__(self) -> str:
		return f"{self.lb}/10^{self.T} <= x <= {self.ub}/10^{self.T}"
	
	def log_inner(self, tar_m: "MyFloat") -> int:
		tar = MyFloat(0, tar_m.T)
		tar.lb = tar_m.lb
		tar.ub = tar_m.ub
		ans = MyFloat(0, tar.T)
		tar.lb *= 10 ** tar.T
		tar.ub *= 10 ** tar.T
		ans.lb -= log10.ub * tar.T
		ans.ub -= log10.lb * tar.T
		while tar.ub >= (10 ** (tar.T + 1)):
			tar.lb = tar.lb // 10
			ans.lb += log10.lb
			tar.ub = (tar.ub + 9) // 10
			ans.ub += log10.ub		
		while tar.lb >= (2 * 10 ** tar.T):
			tar.lb = tar.lb // 2
			ans.lb += log2.lb
			tar.ub = (tar.ub + 1) // 2
			ans.ub += log2.ub
		y = (tar - MyFloat(1, tar.T)) / (tar + MyFloat(1, tar.T))
		var = y * MyFloat(2, tar.T)
		for i in range(20):
			ans += var / MyFloat(2 * i + 1, tar.T)
			var = var * y * y
		return ans.lb
	
	def log(self) -> "MyFloat":
		ans = MyFloat(0, self.T)
		ans.lb = self.log_inner(self)
		ans.ub = - self.log_inner(MyFloat(1, self.T) / self)
		return ans

cst = 180

log10    = MyFloat(0, cst)
log10.lb = 2302585092994045684017991454684364207601101488628772976033327900967572609677352480235997205089598298341967784042286248633409525465082806756666287369098781689482907208325554680843799
log10.ub = 2302585092994045684017991454684364207601101488628772976033327900967572609677352480235997205089598298341967784042286248633409525465082806756666287369098781689482907208325554680843800

log2     = MyFloat(0, cst)
log2.lb  =  693147180559945309417232121458176568075500134360255254120680009493393621969694715605863326996418687542001481020570685733685520235758130557032670751635075961930727570828371435190307
log2.ub  =  693147180559945309417232121458176568075500134360255254120680009493393621969694715605863326996418687542001481020570685733685520235758130557032670751635075961930727570828371435190308

gamma = MyFloat(0, cst)
gamma.lb =  577215664901532860606512090082402431042159335939923598805767234884867726777664670936947063291746749514631447249807082480960504014486542836224173997644923536253500333742937337737673
gamma.ub =  577215664901532860606512090082402431042159335939923598805767234884867726777664670936947063291746749514631447249807082480960504014486542836224173997644923536253500333742937337737674

"""
cst = 40
log10    = MyFloat(0, cst)
log10.lb = 23025850929940456840179914546843642076011
log10.ub = 23025850929940456840179914546843642076012

log2     = MyFloat(0, cst)
log2.lb  = 6931471805599453094172321214581765680755
log2.ub  = 6931471805599453094172321214581765680756

gamma = MyFloat(0, cst)
gamma.lb =  5772156649015328606065120900824024310421
gamma.ub =  5772156649015328606065120900824024310422
"""

mx = 2000000
H_table = [MyFloat(0, cst)] * (mx + 1)

def H(n: int) -> "MyFloat":
	if n < 0: return MyFloat(0, cst)
	if n <= mx: return H_table[n]
	ret = MyFloat(0, cst)
	ret.lb = (MyFloat.log(MyFloat(n, cst)) + gamma + MyFloat(1, cst) / (MyFloat(n, cst) * MyFloat(2, cst)) - MyFloat(1, cst) / (MyFloat(n, cst) * MyFloat(n, cst) * MyFloat(8, cst))).lb
	ret.ub = (MyFloat.log(MyFloat(n, cst)) + gamma + MyFloat(1, cst) / (MyFloat(n, cst) * MyFloat(2, cst))).ub
	return ret

for i in range(1, mx+1):
	H_table[i] = H_table[i-1] + MyFloat(1, cst) / MyFloat(i, cst)
	if i % (mx // 100) == 0:
		print(i)

n = int(input())
ans = MyFloat(0, cst)
i = n
itr = 0
while i > 0:
	v = n // i
	j = n // (v + 1)
	ans += H(v) * (H(i) - H(j))
	i = j
	itr += 1
	if itr % 100 == 0: print(itr)

print(ans)
0