結果

問題 No.2834 Work to Play
コンテスト
ユーザー Sinonen
提出日時 2024-06-18 15:49:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 109 ms / 2,000 ms
コード長 1,206 bytes
コンパイル時間 366 ms
コンパイル使用メモリ 82,452 KB
実行使用メモリ 75,492 KB
最終ジャッジ日時 2024-06-18 16:09:37
合計ジャッジ時間 7,632 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 89
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

N,A,K=list(map(int,input().split()))
MOD=998244353
inv6=pow(6,MOD-2,MOD)
inv2=pow(2,MOD-2,MOD)
def gcd(A,B):
  if B==0:
    return A
  else:
    return gcd(B,A%B)
g=gcd(A,K)
A=A//g
K=K//g

def Remove1(N,A,K):
  cnt=0
  for b in range(min(K,N+1)):
    r=(N-b)//K
    C=(b*A)//K
    cnt=(cnt+K*A*inv6*r*(r+1)*(2*r+1)+(b*A+K*C)*inv2*r*(r+1)+b*C*(r+1))%MOD
    #print(b,cnt,r)
  return cnt
  
def Remove2(N,A,K):
  c=0
  M=0
  now=0
  ok=1
  ok2=0
  for i in range(N,N-2*K,-1):
    if i<=0:
      ok=0
      break
    if ok2==0:
      if (A*i)%K!=0:
        ok2=1
        now=(A*i)%K
        c+=1
        M-=(N-i)
    else:
      now=(now+(A*i)%K)
      if now>K:
        now-=K
        c+=1
        M-=(N-i)
  if ok==0:
    return 0
  else:
    r=N//(2*K)-1
    #print(r,c,M)
    return ((N*c+M)*(r+1)-2*K*c*inv2*r*(r+1))%MOD
    
def Remove3(N,A,K):
	cnt=0
	now=0
	ok=0
	for i in range(N,0,-1):
		if ok==0 and (A*i)%K!=0:
			cnt+=i
			ok=1
			now=(A*i)%K
		elif ok==1:
			now+=(A*i)%K
			if now==K:
				now=0
				ok=0
			if now>K:
				now-=K
				cnt+=i
	return cnt%MOD
#print(Remove1(N,A,K),Remove2(N,A,K),Remove3(N%(2*K),A,K))	
ans=(Remove1(N,A,K)+Remove2(N,A,K)+Remove3(N%(2*K),A,K))%MOD
print((ans*2)%MOD)
0