結果

問題 No.3478 XOR-Folding Primes
コンテスト
ユーザー ああ
提出日時 2026-03-23 00:25:00
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 3,719 ms / 4,000 ms
コード長 970 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 377 ms
コンパイル使用メモリ 85,328 KB
実行使用メモリ 243,784 KB
最終ジャッジ日時 2026-03-23 00:25:17
合計ジャッジ時間 16,176 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

x=[0]*10**7
s=set()
p=[0]
h=[0,2]
def aa(mat,n,q):
	global mod
	c=[[0]*3 for i in range(3)]
	c[0][0]=1;c[1][1]=q;c[2][2]=q
	while n:
		if n&1:
			c=bb(c,mat)
		n>>=1
		mat=bb(mat,mat)
	ans=0
	for i in range(3):
		for j in range(3):
			ans+=c[i][j]
	print(ans%mod)
def bb(q,w):
	global mod
	e=[[0]*3 for i in range(3)]
	for i in range(3):
		for j in range(3):
			for l in range(3):
				e[j][l]+=q[j][i]*w[i][l]%mod;e[j][l]%=mod
	return e
mod=998244353
for i in range(3,len(x),2):
	if x[i]:
		continue
	x[i]=1
	s.add(i)
	h.append(i)
	if i^2 in s:
		p.append(i)
	for j in range(i,len(x),i):
		x[j]=1
for _ in range(int(input())):
	n,m=map(int,input().split())
	if n==1:
		q,w=0,len(h)
		while w-q>1:
			s=(q+w)//2
			if h[s]<=m:
				q=s
			else:
				w=s
		print(q)
		continue
	mat=[[0]*3 for i in range(3)]
	mat[1][2]=1;mat[2][1]=1
	mat[1][0]=1;mat[2][0]=1
	q,w=0,len(p)
	while w-q>1:
		s=(q+w)//2
		if p[s]<=m:
			q=s
		else:
			w=s
	mat[0][1]=q;mat[0][2]=q
	aa(mat,n-1,q)
0