蓝桥杯备战日志(Python)2-相乘(逆向枚举)

原题

小蓝发现，他将  至  之间的不同的数与  相乘后再求除以  的余数，会得到不同的数。 小蓝想知道，能不能在  至  之间找到一个数，与  相乘后 再除以  后的余数为 。如果存在，请在答案中提交这个数； 如果不存在，请在答案中提交 。

分析

本题可以使用通常的暴力枚举遍历1~1000000007并判断是否有满足条件的数，但时间复杂度太大。我们进行“逆向枚举”。

• 令n = 1000000007, s = 999999999
• 一般思路在区间[1,1000000007]找到一个x，使得2021*x ÷ n = d ······ s（即2021x除以n等于d,余数为s）
• 枚举x的区间范围较大，不妨转换式子为：2021*x = d*n+ s (d为正整数)，此时可通过x的最小值和最大值求出d的范围
• d的范围为[(2021-s)/n, 2021-s/n]
• 本题中，经过计算，d的取值区间为[1,2020] (d为正整数)，这大大压缩了枚举范围

源码(Python)

n = 1000000007
s = 999999999


for d in range(0,2021):
    x,m = divmod(n*d+s,2021)
    if m == 0:
        print(x)
        break

if m!=0:
    print(0)

上一篇：​​蓝桥杯备战日志(Python)1-卡片&直线(普通填空)​​