結果
問題 | No.1339 循環小数 |
ユーザー |
👑 ![]() |
提出日時 | 2021-01-15 21:51:54 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 164 ms / 2,000 ms |
コード長 | 3,810 bytes |
コンパイル時間 | 443 ms |
コンパイル使用メモリ | 82,288 KB |
実行使用メモリ | 69,004 KB |
最終ジャッジ日時 | 2024-11-26 14:15:14 |
合計ジャッジ時間 | 4,401 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 |
ソースコード
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 __repr__(self):return self.__str__()#+,-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 __le__(self,other):a,p=self.a,self.nb,q=other.a,other.nreturn (a-b)%q==0 and p%q==0def __ge__(self,other):return other<=selfdef __lt__(self,other):return (self<=other) and (self!=other)def __gt__(self,other):return (self>=other) and (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 inverse(self):return self.Modulo_Inverse()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 __rtruediv__(self,other):return other*(self.Modulo_Inverse())#累乗def __pow__(self,other):if isinstance(other,int):u=abs(other)r=Modulo(pow(self.a,u,self.n),self.n)if other>=0:return relse:return r.Modulo_Inverse()else:b,n=other.a,other.nif pow(self.a,n,self.n)!=1:raise Modulo_Error("矛盾なく定義できません.")else:return self**bdef Order(X):"""Xの位数を求める. つまり, X^k=[1] を満たす最小の正整数 k を求める."""R=X.nN=X.nk=2while k*k<=N:if N%k==0:R-=R//kwhile N%k==0:N//=kk+=1if N>1:R-=R//ND=[]k=1while k*k<=R:if R%k==0:D.append(k)D.append(R//k)k+=1a=float("inf")for k in D:if pow(X,k)==1:a=min(a,k)return a#================================================T=int(input())for _ in range(T):N=int(input())while N%2==0:N//=2while N%5==0:N//=5print(Order(Modulo(10,N)))