結果
問題 |
No.3028 No.9999
|
ユーザー |
|
提出日時 | 2025-02-21 23:27:02 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,717 bytes |
コンパイル時間 | 329 ms |
コンパイル使用メモリ | 82,324 KB |
実行使用メモリ | 848,412 KB |
最終ジャッジ日時 | 2025-02-21 23:27:09 |
合計ジャッジ時間 | 6,227 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 3 MLE * 1 -- * 19 |
ソースコード
import math N = int(input()) sieve_limit = int(math.sqrt(N)) prime_factor = [] prime = [] sieve = list(range(2,sieve_limit+1)) j = 0 remainder = N while sieve: factor = sieve[0] prime.append(factor) sieve = [i for i in sieve if i % factor != 0] while remainder % factor == 0: remainder //= factor prime_factor.append(factor) if remainder < factor: break prime_factor.append(remainder) #print(prime) #print(prime_factor) K_limit = math.lcm(*[k-1 for k in prime_factor]) #print(K_limit) remainder = K_limit def prime_factor_search(number): remainder = number factors = [] for factor in prime: while remainder % factor == 0: remainder //= factor factors.append(factor) if remainder > 1: factors.append(remainder) return factors prime_factors = [prime_factor_search(k-1)for k in prime_factor] #print(prime_factors) factor_candidate = {i for row in prime_factors for i in row} def prime_factor_search_candidate(number,candidate): remainder = number factors = [] for factor in candidate: exponent = 0 while remainder % factor == 0: remainder //= factor exponent += 1 if exponent > 0: factors.append((factor,exponent)) return factors K_prime_factor = prime_factor_search_candidate(K_limit,factor_candidate) K_candidate = [1] for factor,exponent in K_prime_factor: K_candidate_new = set() for i in range(exponent+1): K_candidate_new = K_candidate_new | {j*factor**i for j in K_candidate} K_candidate = K_candidate_new #print(K_prime_factor) #print(K_candidate) for _ in range(len(K_candidate)): min_k = min(K_candidate) if 10**min_k % N == 1: print(min_k) break else: K_candidate.remove(min_k) #print(min({k for k in K_candidate if 10**k % N == 1}))