本文为人工撰写,仅使用生成式AI校对。

题目链接

题目:

西小电注意到,第一周的题目中出现了若干神秘数字,并且他还发现这些神秘数字与神秘Flag有关,具体地,xx 是能够满足神秘式子 13x=114514mod  10000000000009913x=114514mod100000000000099 的最小整数,flag内容即为 xx ,你能帮助西小电求出正确的 Flag 吗?

“好奇怪的标题啊,BSGS是什么?北上广深吗?”

注意到BSGS为大步小步算法(baby-step giant-step),是丹尼尔·尚克斯发明的一种中途相遇算法,用于计算离散对数或者有限阿贝尔群的阶。1

代码如下:

import math


mod = 100000000000099
a = 13
b = 114514


n = mod - 1
m = math.isqrt(n) + 1

baby = {}

cur = 1
for j in range(m):
    baby[cur] = j
    cur = cur * a % mod

f = pow(a, -m, mod)

cur = b
for i in range(m):
    if cur in baby:
        print(i * m + baby[cur])
        break
    cur = cur * f % mod

输出:

18272162371285