結果

問題 No.3028 No.9999
コンテスト
ユーザー dp_ijk
提出日時 2025-02-21 21:33:31
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 41 ms / 4,000 ms
コード長 612 bytes
コンパイル時間 275 ms
コンパイル使用メモリ 82,916 KB
実行使用メモリ 58,792 KB
最終ジャッジ日時 2025-02-21 21:33:35
合計ジャッジ時間 2,378 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

def divisors(X):
   from math import isqrt
   assert X >= 1
   head = [d for d in range(1, isqrt(X) + 1) if X%d == 0]
   tail = [X//d for d in reversed(head)]
   if isqrt(X)**2 == X:
      head.pop()
   head.extend(tail)
   return head

def euler_phi(X):
   assert X >= 1
   res = X
   d = 2
   while d*d <= X:
      if X%d == 0:
         res = res//d*(d-1)
         while X%d == 0:
            X //= d
      d += 1
   if X > 1:
      res = res//X*(X-1)
   return res

N = int(input())

D = divisors(euler_phi(N))

for d in D:
   if (pow(10, d, N) - 1) % N == 0:
      print(d)
      break
else:
   assert False
0