//Hash + 扩展欧几里得 +拆分思想
/* 求解模方程a^x=b(mod n),n为素数。
模板题。
时间复杂度O(sqrt(n)*logn)
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
//baby_step giant_step
// a^x = b (mod n) n为素数,a,b < n
// 求解上式 0<=x < n的解
#define MOD 76543
int hs[MOD],head[MOD],next[MOD],id[MOD],top;
//Hash
void insert(int x,int y)
{
int k = x%MOD;
hs[top] = x, id[top] = y, next[top] = head[k], head[k] = top++;
}
int find(int x)
{
int k = x%MOD;
for(int i = head[k]; i != -1; i = next[i])
if(hs[i] == x)
return id[i];
return -1;
}
//baby step giant step
int BSGS(int a,int b,int n)
{
memset(head,-1,sizeof(head));
top = 1;
if(b == 1)return 0;
int m = sqrt(n*1.0), j;
long long x = 1, p = 1;
for(int i = 0; i < m; ++i, p = p*a%n)insert(p*b%n,i);
for(long long i = m; ;i += m)
{
if( (j = find(x = x*p%n)) != -1 )return i-j;
if(i > n)break;
}
return -1;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int a,b,n;
// B ^ L = N (mod P)
while(scanf("%d%d%d",&n,&a,&b) == 3)// P B N
{
int ans = BSGS(a,b,n);
if(ans == -1)printf("no solution
");
else printf("%d
",ans);
}
return 0;
}
当p不为素数时,扩展bsgs. 当然也可以解决p为素数的
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn = 65535;
struct hash{
int a,b,next;
}Hash[maxn << 1];
int flg[maxn + 66];
int top,idx;
//hash值插入
void ins(int a,int b){
int k = b & maxn;
if(flg[k] != idx){
flg[k] = idx;
Hash[k].next = -1;
Hash[k].a = a;
Hash[k].b = b;
return ;
}
while(Hash[k].next != -1){
if(Hash[k].b == b) return ;
k = Hash[k].next;
}
Hash[k].next = ++ top;
Hash[top].next = -1;
Hash[top].a = a;
Hash[top].b = b;
}
//hash值查找
int find(int b){
int k = b & maxn;
if(flg[k] != idx) return -1;
while(k != -1){
if(Hash[k].b == b) return Hash[k].a;
k = Hash[k].next;
}
return -1;
}
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
//扩展欧几里得
int ext_gcd(int a,int b,int& x,int& y)
{
int t,ret;
if (!b){x=1,y=0;return a;}
ret=ext_gcd(b,a%b,x,y);
t=x,x=y,y=t-a/b*y;
return ret;
}
// 求逆元
int Inval(int a,int b,int n){
int x,y,e;
ext_gcd(a,n,x,y);
e=(LL)x*b%n;
return e<0?e+n:e;
}
int pow_mod(LL a,int b,int c)
{
LL ret=1%c;
a%=c;
while(b){
if(b&1)ret=ret*a%c;
a=a*a%c;
b>>=1;
}
return ret;
}
//求解a^x = b (mod n) a, n互质
int BabyStep(int A,int B,int C){
top = maxn; ++ idx;
LL buf=1%C,D=buf,K;
int i,d=0,tmp;
for(i=0;i<=100;buf=buf*A%C,++i)
if(buf==B)return i;
while((tmp=gcd(A,C))!=1){
if(B%tmp)return -1;
++d;
C/=tmp;
B/=tmp;
D=D*A/tmp%C;
}
int M=(int)ceil(sqrt(C+0.5));
for(buf=1%C,i=0;i<=M;buf=buf*A%C,++i)
ins(i,buf);
for(i=0,K=pow_mod((LL)A,M,C);i<=M;D=D*K%C,++i){
tmp=Inval((int)D,B,C);
int w ;
if(tmp>=0&&(w = find(tmp)) != -1) return i*M+w+d;
}
return -1;
}
int main(){
int A,B,C;
// K ^ D == N (mod P)
while(scanf("%d%d%d",&A,&C,&B)!=EOF){// K P N
if(B>C){
puts("Orz,I can’t find D!");
continue;
}
int tmp=BabyStep(A,B,C);
if(tmp<0)
puts("Orz,I can’t find D!");
else printf("%d
",tmp);
}
return 0;
}
2.原根 // 一般原根都很小
/* 求出n中所有的原根,若没有则直接输出-1*/
const int N = 1000000;
bool f[N];
//计算欧拉筛复杂度为 根号n
int phi(int x){
if(f[x]) return x-1;
int ans = x;
for(int i=2; i<=x; i++){
if(x%i==0){
while(x%i==0) x/=i;
ans = ans - ans/i;
}
}
if(x>1) ans = ans - ans/x;
return ans;
}
int gcd(int a, int b){
swap(a,b);
int c = a%b;
while(c){
a=b; b=c; c=a%b;
}
return b;
}
int quick_mod(int x, int p, int mod){
long long s = 1;
long long a = x;
while(p){
if(p&1) s = (s*a)%mod;
a = a*a%mod;
p>>=1;
}
return (int)s;
}
vector<int> V;
vector<int> G;
void cal(int x){
G.clear();
if(f[x]) return;
else{
for(int i=2; i*i<=x; i++){
if(x%i==0){
G.push_back(i);
if(i*i!=x) G.push_back(x/i);
}
}
}
}
//单次检验的复杂度为 log^2 n
bool exist(int n){
if(n%2==0) n/=2;
if(f[n]) return 1;
for(int i=3; i*i<=n; i+=2){
if(n%i==0){
while(n%i==0) n/=i;
return n==1;
}
}
return 0;
}
void solve(int n){
if(n==2){
puts("1");
return;
}
if(n==4){
puts("3");
return;
}
if(!exist(n)){
puts("-1");
return;
}
int p = phi(n);
cal(p);
int x = -1;
for(int i=2; ibool flag = 1;
if(quick_mod(i, p, n)!=1) continue;
for(int j=0; jif(quick_mod(i, G[j], n)==1){
flag = 0;
break;
}
}
if(flag){
V.resize(1);
V[0] = x = i;
break;
}
}
if(x==-1){
puts("-1");
return;
}
for(int i=2; iif(gcd(i, p)==1) V.push_back(quick_mod(x, i, n));
}
sort(V.begin(), V.end());
vector<int>::iterator it=unique(V.begin(), V.end());
V.erase(it, V.end());
for(int i=0; iif(i) putchar(' ');
printf("%d", V[i]);
}
puts("");
}
int main(){
memset(f, 1, sizeof(f));
f[0] = f[1] = 0;
for(int i=2; iif(f[i]){
for(int j=i<<1; j0;
}
}
int n;
while(~scanf("%d", &n)) solve(n);
return 0;
}