2023牛客暑期多校10 C

题目链接

题意：给定两个数 求最大的 使得 与 循环同构 。

题解：对于一个数 ，可以拆分成 ，其中 表示数字 的长度。因此，对于符合条件的 ，存在一种分割方式使得 。

简单变形后得到

分别枚举 找出该情况下的 ，不断更新答案即可

对于 ， 下界为 ，上界为 ，同理 下界为 ，上界为 。

设此时

有 (此处约去公因数是为了让 尽可能大)

不妨设 故 有解当且仅当在当前 下存在 。

由于题目要求最大值，所以在给定的 下计算最大的 即可。

于是 。 接下来检查 是否符合条件即可

import math
s = input()
n = len(s)
S = int(s)
k = int(input())
ans = 0
for la in range(1, n):
    for lb in range(1, n - la + 1):
        al = 10 ** (la - 1)
        A = al * 10
        B = 10 ** lb
        mxa = A - 1
        mxb = B - 1
        if la + lb == n :
            mxa = min(mxa, S // B)
        p = B * k - 1
        q = A - k
        if p > 0 and q > 0:
            d = math.gcd(p, q)
            q = q // d
            p = p // d
            cnta = mxa // q
            cntb = mxb // p
            c = min(cnta, cntb)
            if c == 0:
                continue
                 
            a = q * c
            b = p * c
            if al <= a:
                cur_ans = a * B + b
                if cur_ans <= S:
                    ans = max(ans, cur_ans)
                else:
                    a -= q
                    b -= p
                    if al <= a:
                        cur_ans = a * B + b
                        if cur_ans <= S:
                            ans = max(ans,cur_ans)
print(ans)