結果

問題 No.3478 XOR-Folding Primes
コンテスト
ユーザー 👑 p-adic
提出日時 2026-03-21 08:19:52
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 921 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 268 ms
コンパイル使用メモリ 85,504 KB
実行使用メモリ 268,824 KB
最終ジャッジ日時 2026-03-21 08:20:46
合計ジャッジ時間 35,255 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

R=range
J=lambda:list(map(int,input().split()))
P=[2,3,5,7,11]
def MillerRabin(n):
	assert n>0
	if n<2:return 0
	if n in P:return 1
	if any(n%p<1 for p in P):return 0
	u,v=n-1,0
	while u&1<1:u>>=1;v+=1
	for p in P:
		m=pow(p,u,n)
		if m!=1:
			for e in R(v):
				if m==n-1:break
				m=m*m%n
			else:return 0
	return 1
Q=[2]
T=[]
for p in R(3,10**7):
	if MillerRabin(p):
		Q.append(p)
		if(p>>1)&1<1 and MillerRabin(p|2):T.append(p)
B=998244353
def Act(X,v,n):
	L=len(v)
	while n:
		if n&1:v=[sum(a[j]*v[j]for j in R(L))%B for a in X]
		X=[[sum(a[j]*X[j][k]for j in R(L))%B for k in R(L)]for a in X]
		n>>=1
	return v
for t in R(sum(J())):
	N,M=J()
	if N==1:
		l,r=0,len(Q)
		while l<r-1:
			m=(l+r)>>1
			if Q[m]>M:r=m
			else:l=m
		print(l+1)
	else:
		l,r=0,len(T)
		while l<r-1:
			m=(l+r)>>1
			if T[m]>M:r=m
			else:l=m
		if T[l]|2>M:L=l*2
		else:L=l*2+2
		v=[1,L]
		X=[[0,1],[L,1]]
		v=Act(X,v,N-1)
		print(sum(v)%B)
0