$N$次剩余
N 次剩余
求解形如
$$ x^k\equiv b\pmod m $$
的方程, 除 $x$ 外给定.其实本来 $k$ 应该是 $N$, 结果嫌丑就改掉了.
前置知识
基本数论知识, 原根, 扩欧,BSGS, 中国剩余定理.
对于 $m\in\mathbb P$ 的情况
记 $p=m$.
例题
给出 $k,b,p$, 求 $x$ 满足 $x^k\equiv b\pmod m$. 保证 $p\in\mathbb P$.
输入格式
$t+1$ 行. 第 $1$ 行 $1$ 个数 $t$, 表示数据组数. 之后每行一组数据,$3$ 个以空格隔开的数, 依次为 $k,b,p$, 意义如上所述.
输出格式
$t$ 行, 每行从小到大依次输出所有可能的 $x$ 的取值, 空格隔开. 如果 $x\in\empty$, 输出空行.
样例输入
2
2 1 5
2 2 7样例输出
1 4
3 4数据包下载 (20.3 KB)
求 $g$ 为 $p$ 的原根
原根的性质
若 $g$ 是 $p\in\mathbb P$ 的原根, 则 $\forall i\not=j,i,j\in\{1,2,\cdots,m-1\}\Rightarrow g^i\not\equiv g^j\pmod p$. 说人话: 对于任意 $1\le i<m$ 的整数 $i$,$g^i\bmod p$ 的值两两不同. 此时 $g^i\equiv1\pmod p\Leftrightarrow i=m-1$.
目前看来求原根的主要方法是从 $2$ 开始枚举, 然后暴力判断每一个 $g^i\bmod p$ 是否为 $1$. 有一个小优化就是先唯一分解 $g=q_0^{a_0}\cdot q_1^{a_1}\cdot\cdots$, 然后判断 $g^{(p-1)/q_i}\bmod p$ 是否为 $1$.
Code
inline bool check(ll a,ll b,vector<ll> &c) {
for (auto i:c) if (ksm(a,(b-1)/i,b)==1)
return false; return true;
}
inline ll groot(ll a) {
ll x=a-1; vector<ll> r;
for (ll i=2;i<=x/i;++i) if(!(x%i)) {
r.push_back(i); while (!(x%i)) x/=i;
}
if (x!=1) r.push_back(x);
for (x=2;;++x) if (check(x,a,r)) return x;
}将 $x^k,b$ 用 $g$ 表示
对于 $x^k\equiv b\pmod p$, 如果有 $x\equiv g^i\pmod p,b\equiv g^j\pmod p$, 则原式显然可以转化为 $g^{ik}\equiv g^j\pmod p$, 这样求解 $ik=j\pmod{p-1}$ 即可得到 $g^i$.
所以这个时候就要用到 BSGS 来求 $g^j\equiv b\pmod p$.
Code
inline ll nxkp(ll a,ll b,ll c) {
unordered_map<ll,ll> h; h.clear();
ll t=(ll)ceil(sqrt(c)),w=ksm(a,t,c);
for (ll i=0;i<t;++i)
h[b*ksm(a,i,c)%c]=i;
if (!ksm(a,t,c)) return b?-1:1;
for (ll i=1,j=w;i<=t;++i,j=j*w%c)
if (h.count(j)) return i*t-h[j];
return -1;
}求解 $x$
求解 $i$
这个时候窝们已经得到了线性同余方程 $ik\equiv j\pmod{p-1}$, 用扩欧求解出 $i$ 即可.
然而 $i$ 不止一个值, 对于 $x=g^i\bmod p$ 而言, 多个 $i$ 的值都是合法的, 所以窝想到的办法是开一个unordered_map来记录解集中有没有这个 $x$: 没有就将这个 $x$ 加入解集, 然后求下一个 $i$; 有就说明找到了循环, 返回.
Code
inline vector<ll> xnkp(ll a,ll b,ll c) {
vector<ll> r; unordered_map<ll,ll> p;
ll g=groot(c),w,e,x,y;
if (!b) {r.push_back(0); return r;}
else if ((!(a%=(c-1)))&&b!=1) return r;
w=(nxkp(g,b,c)+c-1)%(c-1);
e=exgcd(a,c-1,x,y); if (w%e) return r;
x=(x*w/e)%(c-1); y=(c-1)/e;
if (x<0) x+=((-x)/y+((-x)%y?1:0))*y;
for (;!p.count(w=ksm(g,x,c));x+=y) {
r.push_back(w); p[w]=x;
}
sort(r.begin(),r.end());
return r;
}Code
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long ll;
const ll inf=0x7fffffffffffffff;
namespace prime{
int c; ll p[100005]; bool f[100005];
void getprime() {
for(ll i=2;i<100002;++i) {
if(!f[i]) p[c++]=i;
for(int j=0;j<c;++j) {
if(i*p[j]>100001) break;
f[i*p[j]]=false;
if(!(i%p[j])) break;
}
}
}
}
inline ll ksm(ll a,ll b,ll c) {
ll r=1; while (b) {
if (b&1) r=r*a%c;
a=a*a%c; b>>=1;
}
return r;
}
inline ll exgcd(ll a,ll b,ll &x,ll &y) {
if (!b) {x=1; y=0; return a;}
ll c=exgcd(b,a%b,x,y);
ll z=x; x=y; y=z-y*(a/b);
return c;
}
inline bool check(ll a,ll b,vector<ll> &c) {
for (auto i:c) if (ksm(a,(b-1)/i,b)==1)
return false; return true;
}
inline ll groot(ll a) {
ll x=a-1; vector<ll> r;
for (ll i=2;i<=x/i;++i) if(!(x%i)) {
r.push_back(i); while (!(x%i)) x/=i;
}
if (x!=1) r.push_back(x);
for (x=2;;++x) if (check(x,a,r)) return x;
}
inline ll nxkp(ll a,ll b,ll c) {
unordered_map<ll,ll> h; h.clear();
ll t=(ll)ceil(sqrt(c)),w=ksm(a,t,c);
for (ll i=0;i<t;++i)
h[b*ksm(a,i,c)%c]=i;
if (!ksm(a,t,c)) return b?-1:1;
for (ll i=1,j=w;i<=t;++i,j=j*w%c)
if (h.count(j)) return i*t-h[j];
return -1;
}
inline vector<ll> xnkp(ll a,ll b,ll c) {
vector<ll> r; unordered_map<ll,ll> p;
ll g=groot(c),w,e,x,y;
if (!b) {r.push_back(0); return r;}
else if ((!(a%=(c-1)))&&b!=1) return r;
w=(nxkp(g,b,c)+c-1)%(c-1);
e=exgcd(a,c-1,x,y); if (w%e) return r;
x=(x*w/e)%(c-1); y=(c-1)/e;
if (x<0) x+=((-x)/y+((-x)%y?1:0))*y;
for (;!p.count(w=ksm(g,x,c));x+=y) {
r.push_back(w); p[w]=x;
}
sort(r.begin(),r.end());
return r;
}
int main() {
int t; ll a,b,c; vector<ll> x;
prime::getprime();
scanf("%d",&t); while (t--) {
scanf("%lld%lld%lld",&a,&b,&c);
x=xnkp(a,b,c);
for (auto i:x) printf("%lld ",i);
printf("\n");
}
return 0;
}对于 $m\not\in\mathbb P$ 的情况
不会, 咕了.
