专栏文章

题解：P10496 The Luckiest Number

QQZKago_Req
P10496题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqgcmmb
此快照首次捕获于
2025/12/04 04:21
3 个月前
此快照最后确认于
2025/12/04 04:21
3 个月前
查看原文

题意

给定 LL，求 min⁡L∣89(10x−1){x}\min\limits_{L\mid\dfrac{8}{9}(10^x-1)}\{x\}。

题解

先推式子：
L∣89(10x−1)L\mid\dfrac{8}{9}(10^x-1)
9L∣8(10x−1)9L\mid8(10^x-1)
9Lgcd⁡(L,8)∣10x−1\frac{9L}{\gcd(L,8)}\mid10^x-1
10x≡1(mod9Lgcd⁡(L,8))10^x\equiv1\pmod{\frac{9L}{\gcd(L,8)}}
根据小学二年级知识，若 a,na,n 互质，则 φ(n)∣(min⁡ax≡1(modn){x})\varphi(n)\mid\left(\min\limits_{a^x\equiv1\pmod{n}}\{x\}\right)。
证明可以用反证法。
所以只需求 φ(9Lgcd⁡(L,8))\varphi\left(\dfrac{9L}{\gcd(L,8)}\right)，枚举其因数，判断是否满足条件即可，时间复杂度 O(Llog⁡L)O(\sqrt{L}\log L)。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...