给定整数K和质数m，求最小的正整数N，使得 11111⋯1（N个1） mod m≡K(modm)
说人话：就是 111…1111 mod m =K
思路：我们可以给左右两边同乘上99再加上11，因为膜运算的性质，因此这样做这个同余方程还是成立的。
然后问题就瞬间转化为：
给定整数K和质数m，求最小的正整数N，使得10^N ≡K(modm) （BSGS模板题）
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll p, a, b; ll qmul(ll a, ll b, ll mod) { ll ans = 0; while (b) { if (b & 1) { ans = (ans + a) % mod; } a = (a + a) % mod; b >>= 1; } return ans % mod; } int main() { cin >> b >> p; a = 10; b = b * 9 + 1; b %= p; ll n = sqrt(p) + 1; map<ll,ll> mp; ll ans = b%p; for (int i = 0; i <= n; i++) { mp[ans] = i; ans = qmul(ans, a, p); } ans = 1; for (int i = 1; i <= n; i++) ans = qmul(ans, a, p); ll ret = 1; for (int i = 1; i <= n; i++) { ret = qmul(ret, ans, p); if (mp[ret] != 0) { cout << (ll)i * n - mp[ret] << endl; return 0; } } return 0; }
