给定p和模数yyb,保证yyb为质数,求最小的x使得111⋯1(x个)≡1(modyyb)
链接
题解
注意到111⋯1(x个)=10x−19,则
111⋯1≡(10x−1)×9−1∴(10x−1)×9−1≡yyb∴10x≡9×yyb+1然后这个方程就化为BSGS的标准形式了,由于模数yyb为质数,直接利用BSGS即可。
由于yyb会很大,所以再次建议不要用自己写的哈希表,而使用map。我是不会告诉你我因为这个原因被洛谷的数据坑了好几次了
代码
为了保险,这里开了int128,美中不足的是要自己写读写,顺便写了一个O(1)的龟速乘。
1 |
|
v1.5.2