[题解]gdfzoj2141 奇怪的题目3

传送门

原题

题目里的 (111...11) 让人很不爽

设 (111...11) 为 (x)

(ecause x equiv k (mod m))

( herefore x*9+1 equiv k*9+1 (mod m))

( herefore 10^n equiv k*9+1 (mod m))

然后就可以愉快地用 北上广深拔山盖世（误） (BSGS) 切了这道题了

有个 毒瘤 值得注意的点是这题快速幂的时候会爆 (ll) ， 所以我用__int128

当然这道题时限很宽，用龟速幂也是可以过的

想学 (BSGS) 的童鞋可以左转 yyb的博客

代码（巨丑无比）

（千万别学我的样子写 (BSGS) ，我的常数贼大，差点被我自己出的数据卡了 /fad)