結果

問題 No.3651 K-th Sum of Divisors
コンテスト
ユーザー p-adic
提出日時 2026-07-22 09:57:45
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 86 ms / 2,000 ms
+ 494µs
コード長 1,045 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 323 ms
コンパイル使用メモリ 96,240 KB
実行使用メモリ 84,864 KB
最終ジャッジ日時 2026-08-28 21:04:30
合計ジャッジ時間 6,854 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class LoopDetection:
	def __init__(self,init,f):
		self.init=init
		self.f=f
		self.value=[]
		self.value_inv={}
		self.loop_start=-1
		self.loop_length=-1

	def IteratedComposition(self,n):
		L=len(self.value)
		if L<1:self.SetValue(self.init)
		if n<L:return self.value[n]
		if self.loop_start!=-1:return self.value[self.loop_start+(n-self.loop_start)%self.loop_length]
		self.SetValue(self.f(self.value[-1]))
		return self.IteratedComposition(n)

	def SearchLoop(self):
		n=0
		while self.loop_length==-1:self.IteratedComposition(n);n+=1
		return

	#private
	def SetValue(self,i):
		L=len(self.value)
		if i in self.value_inv:
			self.loop_start=self.value_inv[i]
			self.loop_length=L-self.loop_start
		else:
			self.value.append(i)
			self.value_inv[i]=L
		return

R=range
O=print
N,K=map(int,input().split())
if K<2:exit(O(N))
B=100003
C=[0]*B
for d in R(1,B):
	for n in R(d,B,d):C[n]=(C[n]+d)%B
D=0
for d in R(1,N+1):
	if N<d*d:break
	if N%d<1:
		if N>d*d:D+=d+N//d
		else:D+=d
O(LoopDetection(D%B,lambda n:C[n]).IteratedComposition(K-2))
0