使用遞歸學習法。
哈希表是一個資料結構，在哈希的基礎上用一個連結清單（我喜歡鄰接表）把對某個數取模相同的東西放在一個起始節點下。
複雜度期望在1左右，或者很小的常數。
給a,b,質數p，求解
先讨論特殊情況。
如果a mod p==0，無解。
如果b%p==1，那x=0就行了。
而大多數情況。
首先因為p是質數，那如果x是一個解，則x%p也是一個解。是以我們隻需要管0<=x<p的解。
對于這p個取值，加入我們确定一個m，将x化成c*m-d。
是以
如果我們将
插入一個哈希表，然後枚舉c，将
丢進去查有沒有相等，這樣複雜度就削下來了。
可以簡單發現m取
時複雜度最小，為根号p。
【SDOI2011】電腦
#include<bits/stdc++.h>
using namespace std;
#define in read()
#define int long long
int in{
int cnt=0,f=1;char ch=0;
while(!isdigit(ch)){
ch=getchar();if(ch=='-')f=-1;
}
while(isdigit(ch)){
cnt=cnt*10+ch-48;
ch=getchar();
}return cnt*f;
}
const int Hastmod=1e5+7;
int n,t;
int y,z,mod;
int ksm(int a,int b){
int sum=1;
while(b){
if(b&1)sum=sum*a%mod;
a=a*a%mod;b>>=1;
}return sum;
}
int first[Hastmod],nxt[Hastmod<<4],key[Hastmod<<4],wz[Hastmod<<4];
int tot;
void add(int a,int b,int c){
nxt[++tot]=first[a];first[a]=tot;key[tot]=b;wz[tot]=c;
}
void Hast(int x,int ri){
int gu=x%Hastmod;
add(gu,x,ri);
}
int calc(int x){
int s=x%Hastmod;
for(int i=first[s];i;i=nxt[i]){
if(key[i]==x)return wz[i];
}return -1;
}
void noans(){
printf("Orz, I cannot find x!\n");
}
void query(){
if(y%mod==0){
noans();return;
}
y%=mod;z%=mod;
if(z==1){
cout<<"0"<<'\n';return;
}
memset(first,0,sizeof(first));tot=0;
int m=sqrt(mod)+1;
for(int i=0,t=z;i<m;i++,t=t*y%mod)Hast(t,i);
for(int i=1,t=ksm(y,m),tt=t;i<=m+1;i++,tt=tt*t%mod){
int k=calc(tt);if(k==-1)continue;
cout<<i*m-k<<'\n';return;
}noans();
}
signed main(){
n=in;t=in;
while(n--){
y=in;z=in;mod=in;
if(t==1){
printf("%lld\n",ksm(y,z));
}
if(t==2){
if(y%mod==0){
noans();continue;
}
printf("%lld\n",ksm(y,mod-2)*z%mod);
}
if(t==3){
query();
}
}
return 0;
}
如果p不是質數，稱為exBSGS。
大體可以這麼了解。
如果d不是b的約數，那麼隻有在b=1時，x有0解，否則無解。
如果是，可以繼續推導
再令d=
,如此循環，直到出現無解或者d=1為止。
此時
第二項可以直接逆元甩過去，然後就是BSGS。
但是答案記得+num。
但是！還有0到num-1需要暴力驗證，反正logn，因為gcd除下來最多log個。
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=31630;//sqrt fai()
const int mod=100003;
ll C,A,B;
ll ni[N];
struct node{
int nxt[mod],val[mod],id[mod],cnt;
int hd[mod];
void init(){
memset(nxt,0,sizeof nxt),memset(val,0,sizeof val),memset(id,0,sizeof id);
memset(hd,0,sizeof hd),cnt=0;
}
void insert(ll x,int d){
int st=x%mod;
for(int i=hd[st];i;i=nxt[i]){
if(val[i]==x) return;
}
val[++cnt]=x,nxt[cnt]=hd[st],id[cnt]=d,hd[st]=cnt;
}
int find(ll x){
int st=x%mod;
for(int i=hd[st];i;i=nxt[i]){
if(val[i]==x) return id[i];
}
return -233;
}
}ha;
void exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1,y=0;return;
}
exgcd(b,a%b,y,x);
y-=(a/b)*x;
}
ll qm(ll a,ll b,ll p){
ll ret=1,base=a;
while(b){
if(b&1) ret=(base*ret)%p;
base=(base*base)%p;
b>>=1;
}
return ret;
}
int gcd(int a,int b){
return (b==0)?a:gcd(b,a%b);
}
int BSGS(ll a,ll b,ll c){
int up=(int)floor(sqrt(1.0*c-1))+1;
ll ni=0,yy=0;
exgcd(qm(a,up,c),c,ni,yy);
ni=(ni%c+c)%c;//warning!!! 必須變成正數
ll kk=1;
for(int i=0;i<=up-1;i++){
ha.insert(kk,i);
kk=(kk*a)%c;
}
ll bb=b;
for(int i=0;i<=up;i++){
int kk=ha.find(bb);
if(kk>=0) return i*up+kk;
bb=(bb*ni)%c;//不斷找逆元 遞推就可以
}
return -233;
}
int EXBSGS(){
int num=0;
int yC=C;
int yB=B;
int yA=A;
ll ji=1;
int ret=-233;
bool flag=false;
while(1){
int g=gcd(A,C);
if(g==1) break;
if(B%g) {
flag=true;break;
}
B/=g,C/=g,ji=(ji*A/g)%C;
num++;
}
for(int i=0;i<=num;i++){
ll kk=qm(yA,i,yC);
if(kk%yC==yB) return i;
}
if(!flag){
ll ni,yy;
exgcd(ji,C,ni,yy);
ni=(ni%C+C)%C;//warning!!! 必須變成正數
ll NB=(B*ni)%C;
ret=BSGS(A,NB,C);
}
if(ret>=0) return ret+num;
else return -233;
}
int main(){
while(1){
scanf("%lld%lld%lld",&A,&C,&B);
if(A==0&&B==0&&C==0) break;
ha.init();
B%=C;
int ret=EXBSGS();
if(ret>=0){
printf("%d\n",ret);
}
else{
puts("No Solution");
}
}
return 0;
}