https://projecteuler.net/problem=26
各に対し、となる最小の自然数を求めます。オイラーの定理からなので、の約数となります。
実際のところは、素数の大きい方から順に調べて、周期がその数より1小さいものがあれば、その素数が求める答えです。
from math import min import sys #################### library #################### def div_pow(n: Int, d: Int) -> Tuple[Int, Int]: var m = n var e = 0 while m % d == 0: e += 1 m //= d return (e, m) def pow(b: Int, e: Int, d: Int) -> Int: if e == 1: return b % d elif e % 2 == 1: return b * pow(b, e-1, d) % d else: var p = pow(b, e//2, d) return p * p % d fn print_vector(v: DynamicVector[Int]): for k in range((v.size + 9) // 10): var s = str("") for i in range(k*10, min(k*10+10, v.size)): s += str(v[i]) + " " print(s) #################### Factors #################### struct Factors(CollectionElement): var fs: DynamicVector[Tuple[Int, Int]] fn __init__(inout self, fs: DynamicVector[Tuple[Int, Int]]): self.fs = fs fn __copyinit__(inout self, other: Factors): self.fs = other.fs fn __moveinit__(inout self, owned other: Factors): self.fs = other.fs^ fn __mul__(self, other: Factors) -> Factors: var fs = DynamicVector[Tuple[Int, Int]]() var L1 = self.fs.size var L2 = other.fs.size var k = 0 var l = 0 while k < L1 and l < L2: var p1 = self.fs[k].get[0, Int]() var p2 = other.fs[l].get[0, Int]() var e1 = self.fs[k].get[1, Int]() var e2 = other.fs[l].get[1, Int]() if p1 == p2: fs.push_back((p1, e1+e2)) k += 1 l += 1 elif p1 < p2: fs.push_back((p1, e1)) k += 1 else: fs.push_back((p2, e2)) l += 1 for k1 in range(k, L1): fs.push_back(self.fs[k1]) for l1 in range(l, L2): fs.push_back(other.fs[l1]) return Factors(fs) @staticmethod fn create(n: Int) raises -> Factors: var fs = DynamicVector[Tuple[Int, Int]]() var m = n for p in range(2, n+1): if p*p > m: break elif m%p == 0: var a = div_pow(m, p) var e = a.get[0, Int]() fs.push_back((p, e)) m = a.get[1, Int]() if m > 1: fs.push_back((m, 1)) return Factors(fs) #################### PrimeTable #################### struct PrimeTable: var table: DynamicVector[Int] fn __init__(inout self, table: DynamicVector[Int]): self.table = table fn factorize(self, n: Int) -> Factors: try: return Factors(self.factorize_core(n)) except: return Factors(DynamicVector[Tuple[Int, Int]]()) fn factorize_core(self, n: Int) raises -> DynamicVector[Tuple[Int, Int]]: if n == 1: return DynamicVector[Tuple[Int, Int]]() var p = self.table[n] var a = div_pow(n, p) var e = a.get[0, Int]() var m = a.get[1, Int]() var fs = DynamicVector[Tuple[Int, Int]]() fs.push_back((p, e)) var fs1 = self.factorize_core(m) for f in fs1: fs.push_back(f[]) return fs @staticmethod def make_min_prime_table(N: Int) -> PrimeTable: var a = DynamicVector[Int]() for i in range(N+1): a.push_back(1) for p in range(2, N+1): if p*p > N: break if a[p] != 1: continue for n in range(p, N+1, p): if a[n] == 1: a[n] = p for n in range(2, N+1): if a[n] == 1: a[n] = n return PrimeTable(a) #################### process #################### fn remove25(n: Int) -> Int: var m = n while m % 2 == 0: m //= 2 while m % 5 == 0: m //= 5 return m fn phi(fs: Factors) -> Int: var m = 1 for f in fs.fs: var p = f[].get[0, Int]() var e = f[].get[1, Int]() m *= (p-1) * p**(e-1) return m fn period(n: Int, table: PrimeTable) raises -> Int: var n1 = remove25(n) if n1 == 1: return 0 var fs1 = table.factorize(n1) var n2 = phi(fs1) var fs2 = table.factorize(n2) var n3 = n2 for f2 in fs2.fs: var p2 = f2[].get[0, Int]() var e2 = f2[].get[1, Int]() for e in range(e2-1, -1, -1): n3 //= p2 if pow(10, n3, n1) != 1: n3 *= p2 return n3 fn make_period_table(N: Int) raises -> DynamicVector[Int]: var table = PrimeTable.make_min_prime_table(N) var periods = DynamicVector[Int]() periods.push_back(0) periods.push_back(0) for n in range(2, N+1): periods.push_back(period(n, table)) return periods fn max_arg(a: DynamicVector[Int]) -> Int: var max_element = a[0] var index = 0 for i in range(1, a.size): if a[i] > max_element: max_element = a[i] index = i return index fn f(N: Int) raises -> Int: var periods = make_period_table(N) return max_arg(periods) fn main() raises: var args = sys.argv() var N = atol(args[1]) print(f(N))