exBSGS

exBSGS

如果A, P/d 仍然不互质, 我们继续取d, 最后有

于是直接BSGS就可以了, 最后记得将答案加上t

void exBSGS(int a, int b){ if(b == 1){ printf("0\n"); return;} int d = gcd(a, p); LL k = 1; int t = 0; while(d != 1){ if(b % d){ printf("No Solution\n"); return;} ++t; b /= d; p /= d; k = (k * (LL)(a/d)) % p; if(b == k){ printf("%d\n", t); return;} d = gcd(a, p); } M.clear(); LL s = b, m = sqrt(p) + 1; for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。