PTA 团体程序设计天梯赛-练习集 L1-046 整除光棍-白红宇的个人博客

PTA 团体程序设计天梯赛-练习集 L1-046 整除光棍

发布日期：2021-05-19 23:51:25 浏览次数：24 分类：精选文章

本文共 678 字，大约阅读时间需要 2 分钟。

为了解决这个问题，我们需要找到一个最小的整数 s 和一个最小的位数 n，使得 x 乘以 s 等于一个由 n 个 1 组成的数字。这个问题可以通过模拟手算除法的竖式方法来解决。

方法思路

问题分析：我们需要找到一个由 1 组成的最小数，使得它能被给定的奇数 x 整除。这个最小数的位数 n 和商 s 就是我们要找的答案。

模拟竖式除法：我们通过模拟除法的过程来构造这个由 1 组成的数。每次将余数乘以 10 再加上 1，直到余数变为 0。

计算 s 和 n：每次循环，我们增加一个 1，所以位数 n 是循环的次数。商 s 则是这个由 1 组成的数除以 x 的结果。

解决代码

x = int(input())
余数 = 0
n = 0
while True:
    余数 = (余数 * 10 + 1) % x
    n += 1
    if 余数 == 0:
        break
y = (10 ** n - 1) // 9
s = y // x
print(f"{s} {n}")

代码解释

读取输入：读取输入的整数 x，它是一个不以 5 结尾的正奇数。

初始化变量：初始化余数为 0，位数 n 为 0。

循环构造余数：每次循环将余数乘以 10 再加上 1，并对 x 取模。直到余数为 0，说明我们找到了一个由 1 组成的数。

计算最终结果：构造由 n 个 1 组成的数 y，计算商 s 和位数 n。

输出结果：输出商 s 和位数 n。

这个方法通过模拟竖式除法的过程，高效地找到满足条件的最小 s 和 n，避免了暴力构造的时间复杂度问题。

上一篇：Python ValueError: File is not a recognized excel file

下一篇：解决搭载win10+ubuntu双系统的电脑在win10系统更新后引导界面消失的问题

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

方法思路

解决代码

代码解释

发表评论

最新留言

关于作者

推荐文章