(luogu4884)多少个1? 发表于 2020-12-06 | 分类于 solution , 数论 原题链接 思路:纯数学题 由于$m$是质数, 所以逆推也成立. 使用BSGS求解即可. (代码中用的是exBSGS但是数据保证只需要用BSGS即可) 需要注意乘法的溢出问题. 代码:1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include <cstdio>#include <cmath>#include <unordered_map>using std::unordered_map;#define int long long //省事:)int gcd(int a,int b) { return b==0 ? a : gcd(b,a%b);}int exgcd(int a,int b,int& x,int& y) { if(b == 0) { x = 1; y = 0; return a; } int g = exgcd(b,a%b,y,x); y -= a/b*x; return g;}int inv(int a,int m) { //求逆 int ret,y; exgcd(a,m,ret,y); return (ret+m)%m;}int exbsgs(int a,int p,int b) { if(b==1) { return 0; } int c = 1,g,k(0); while((g=gcd(a,p))!=1) { if(b%g!=0) { return -1; } c = (__int128)c*(a/g)%p; //注意乘法溢出 b /= g; p /= g; ++k; if(b == 1) { return k; } } b = (__int128)b*inv(c,p)%p; //同上 int m = ceil(sqrt(p)); unordered_map<int,int> e; e[1] = 0; int x = a%p; for(int i(1);i<m;++i) { if(x==b) { return i+k; } if(!e.count(x)) { e[x] = i; } x = (__int128)x*a%p; } int anm = inv(x,p); x = ((__int128)b*anm)%p; for(int i(1);i<=m;++i) { if(e.count(x)) { return i*m + e[x] + k; } x = ((__int128)x*anm)%p; } return -1;}signed main() { int k,m; scanf("%lld %lld",&k,&m); k = (k*9+1)%m; int ans = exbsgs(10,m,k); printf("%lld",ans); return 0;}