Submission #72910944

---

Source Code Expand

import sys
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lii = lambda: list(mii())
MOD = 10**9+7
inf = 1<<64
from math import gcd
import math
def phi(n):
    res = n
    i = 2
    while i*i<=n:
        if n % i == 0:
            res= (res // i) * (i-1)
            while n % i == 0:
                n //= i
        i += 1
    
    if n > 1:
        res = (res // n) * (n-1)
    
    return res

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        return self.smallestRepunitDivByK_general(k, 1)
    def smallestRepunitDivByK_general(self, k: int, repunit: int) -> int:
        # 计算出repunit有多少位
        bit_length = len(str(repunit))
        
        # 首先处理i=0的特殊情况（因为不能对0取模）
        if repunit % k == 0:
            return 1 * bit_length   # 最小的n就是repunit的位数

        # 同余式a * x^i ≡ a (mod k)成立，那么我们有:
        # d = gcd(a, k)
        # d|k, d|a => a` * x^i ≡ a` (mod k`)
        # 其中 a` = a / d, k` = k / d
        # 而同余式 a` * x^i ≡ a` (mod k`) 有解的充分必要条件是:
        # gcd(x, k`) = 1

        '''
        启发自lr580的题解 https://leetcode.cn/problems/smallest-integer-divisible-by-k/solutions/2265460/ju-yi-fan-san-kuo-zhan-dao-geng-da-de-k-i55fc/

        证明：如果a与m互质，那么同余式 a * x^i ≡ a (mod m), i=1, 2, 3... 有解的充分必要条件是 gcd(x, m) = 1
        证明过程如下：
        必要性：
            由欧拉定理可知，若 gcd(x, m) = 1, 则有：
                x^i ≡ 1 (mod m), 其中 i = φ(m)
            两边同乘以 a 得到：
                a * x^i ≡ a (mod m)
            必要性得证。
        充分性：
            已知a与m互质，则在模m意义下，a的逆元a^(-1)存在。
            将同余式两边同乘以a^(-1)，得到：
                x^i ≡ 1 (mod m)
            我们有：
                x * x^(i-1) ≡ 1 (mod m)
            这表明 x^(i-1) 是 x 的逆元。
            逆元存在的充分必要条件是 gcd(x, m) = 1。
            因此，充分性得证。
        '''

        # 这里我们要解决的是同余式：repunit` * 10^bit_length ≡ repunit` (mod k`)
        # 其中 repunit` = repunit / g
        # k_hat = k * (10^bit_length - 1)
        # k` = k_hat / g
        # g = gcd(repunit, k_hat)

        # 利用必要性，验证同余式是否有解
        b = pow(10, bit_length)     # e.g. 10/1000
        p = (b-1) * k               # e.g. 9k/999k

        g = math.gcd(repunit, p)
        repunit //= g
        p //= g
        if math.gcd(b, p) != 1:
            return -1

        # 已知 同余式 repunit` * 10^i ≡ repunit` (mod k`) 有解，最大解为 φ(k`)
        # 枚举所有 φ(k`) 的因子，找到最小的解

        # 计算φ(k`)
        m = phi(p)

        i = 1
        while i * i <= m:
            if m % i == 0 and pow(b, i, p) % p == 1:
                return i * bit_length
            i += 1
        
        i -= 1
        while i > 0:
            if m % i == 0 and pow(b, m//i, p) % p == 1:
                return (m // i) * bit_length
            i -= 1

        return -1       # 理论上不会到达这里
def solve():
    n = ii()
    f = Solution()
    if n<10:
        print(n)
        return
    if n%10==0:
        print(-1)
        return
    ans = []
    for i in range(1,10):
        ans.append(f.smallestRepunitDivByK_general(n,i))
    def check(x):
        return str(x)==''.join(sorted(str(x)))
    mi = -1
    for i in range(1,10000):
        if check(i*n):
            mi = str(i*n)
            break
    for i,d in enumerate(ans):
        if d==-1:
            continue
        if mi==-1:
            mi = str(i+1)*d
        if d<len(mi):
            mi = str(i+1)*d
            continue
        if len(mi)==d:
            if mi>str(i+1)*d:
                mi = str(i+1)*d
    print(mi)
    
    
                    
t = 1
# t = ii()
for _ in range(t):
    solve()

Submission Info

Judge Result