結果
問題 | No.1727 [Cherry 3rd Tune] Stray |
ユーザー |
![]() |
提出日時 | 2021-10-29 22:20:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 38 ms / 6,000 ms |
コード長 | 539 bytes |
コンパイル時間 | 294 ms |
コンパイル使用メモリ | 82,568 KB |
実行使用メモリ | 52,864 KB |
最終ジャッジ日時 | 2024-10-07 11:49:47 |
合計ジャッジ時間 | 1,076 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 8 |
ソースコード
from math import gcdmod=10**9+7T=int(input())def solve(N,C):ANS=pow(C,N,mod)*N%modP=[]for i in range(1,int(N**0.5)+1):if N%i==0:P.append(i)if i*i!=N:P.append(N//i)P=sorted(set(P))L=len(P)X=[0]*Lfor i in range(L-1,-1,-1):X[i]=N//P[i]for j in range(i+1,L):if P[j]%P[i]==0:X[i]=X[i]-X[j]for i in range(L):x=pow(C,P[i],mod)ANS=(ANS+x*x*X[i])%modreturn ANS*pow(N*2,mod-2,mod)%modfor t in range(T):N,C=map(int,input().split())print(solve(N,C))