結果
問題 | No.1252 数字根D |
ユーザー |
👑 ![]() |
提出日時 | 2020-08-16 16:50:28 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,930 bytes |
コンパイル時間 | 741 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 77,056 KB |
最終ジャッジ日時 | 2024-11-07 14:21:06 |
合計ジャッジ時間 | 2,478 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 2 WA * 12 |
ソースコード
class Modulo_Error(Exception):passclass Modulo():def __init__(self,a,n):self.a=a%nself.n=ndef __str__(self):return "{} (mod {})".format(self.a,self.n)#+,-def __pos__(self):return selfdef __neg__(self):return Modulo(-self.a,self.n)#等号,不等号def __eq__(self,other):if isinstance(other,Modulo):return (self.a==other.a) and (self.n==other.n)elif isinstance(other,int):return (self-other).a==0def __neq__(self,other):return not(self==other)#加法def __add__(self,other):if isinstance(other,Modulo):if self.n!=other.n:raise Modulo_Error("異なる法同士の演算です.")return Modulo(self.a+other.a,self.n)elif isinstance(other,int):return Modulo(self.a+other,self.n)def __radd__(self,other):if isinstance(other,int):return Modulo(self.a+other,self.n)#減法def __sub__(self,other):return self+(-other)def __rsub__(self,other):if isinstance(other,int):return -self+other#乗法def __mul__(self,other):if isinstance(other,Modulo):if self.n!=other.n:raise Modulo_Error("異なる法同士の演算です.")return Modulo(self.a*other.a,self.n)elif isinstance(other,int):return Modulo(self.a*other,self.n)def __rmul__(self,other):if isinstance(other,int):return Modulo(self.a*other,self.n)#Modulo逆数def Modulo_Inverse(self):x0, y0, x1, y1 = 1, 0, 0, 1a,b=self.a,self.nwhile b != 0:q, a, b = a // b, b, a % bx0, x1 = x1, x0 - q * x1y0, y1 = y1, y0 - q * y1if a!=1:raise Modulo_Error("{}の逆数が存在しません".format(self))else:return Modulo(x0,self.n)#除法def __truediv__(self,other):return self*other.Modulo_Inverse()#累乗def __pow__(self,m):u=abs(m)r=Modulo(1,self.n)while u>0:if u%2==1:r*=selfself*=selfu=u>>1if m>=0:return relse:return r.Modulo_Inverse()#---------------------------------------------------------------------M=10**9+7T=int(input())J=Modulo(1,M)/Modulo(2,M)def g(N):if N==0:return Modulo(0,M)if N%(D-1)==0:Q=Modulo(N//(D-1),M)R=Modulo(0,M)else:Q=Modulo(N//(D-1)+1,M)R=Modulo(D-1-N%(D-1),M)return Q*(E*(E-1))*J-E*R+(R*(R+1))*JX=[0]*Tfor k in range(T):D,A,B=map(int,input().split())E=Modulo(D,M)X[k]=(g(B)-g(max(A-1,0))).aprint("\n".join(map(str,X)))