** The question ： give k,m,newx Value , Find the equation x^k(mod m)=newx Solution , among m As a prime number .**

** Solution steps ：**

**(1) First, please m The original root g**

**(2) Big step, small step g^t1(mod m)=newx**

**(3) be g^(t1+n*t2)(mod m)=newx,t2=m-1**

**(4)x=g^y(mod m),x^k=(g^y)^k=g^(yk)=g^(t1+n*t2)**

** So it's the same equation yk=t1(mod t2), Find out y And then bring in x=g^y(mod m) figure out x**

#include <iostream>

#include <string.h>

#include <algorithm>

#include <stdio.h>

#include <math.h>

#include <map> using namespace std;

typedef long long LL; const int N=1000005; int p[N];

bool prime[N];

int num,cnt;

LL k,m,newx,g;

LL a[65],b[65]; void isprime()

{

num=0;

int i,j;

memset(prime,true,sizeof(prime));

for(i=2;i<N;i++)

{

if(prime[i])

{

p[num++]=i;

for(j=i+i;j<N;j+=i)

{

prime[j]=false;

}

}

}

} LL multi(LL a,LL b,LL m)

{

LL ans=0;

while(b)

{

if(b&1)

{

ans=(ans+a)%m;

b--;

}

b>>=1;

a=(a+a)%m;

}

return ans;

} LL quick_mod(LL a,LL b,LL m)

{

LL ans=1;

a%=m;

while(b)

{

if(b&1)

{

ans=multi(ans,a,m);

b--;

}

b>>=1;

a=multi(a,a,m);

}

return ans;

} void factor(LL n)

{

cnt=0;

for(int i=0;(LL)p[i]*p[i]<=n;i++)

{

if(n%p[i]==0)

{

a[cnt]=p[i];

int c=0;

while(n%p[i]==0)

{

c++;

n/=p[i];

}

b[cnt++]=c;

}

}

if(n>1)

{

a[cnt]=n;

b[cnt++]=1;

}

} LL extend_Euclid(LL a,LL b,LL &x,LL &y)

{

if(b==0)

{

x=1;

y=0;

return a;

}

LL gd=extend_Euclid(b,a%b,x,y);

LL temp=x;

x=y;

y=temp-(a/b)*y;

return gd;

} LL Inv(LL n,LL p)

{

return quick_mod(n,p-2,p);

} bool dfs(int dept,LL t)

{

if(dept==cnt)

{

LL ans=quick_mod(g,t,m);

if(ans==1&&t!=m-1) return false;

return true;

}

LL tmp=1;

for(int i=0;i<=b[dept];i++)

{

if(!dfs(dept+1,t*tmp)) return false;

tmp*=a[dept];

}

return true;

} void find()

{

factor(m-1);

for(g=2;;g++)

if(dfs(0,1)) break;

} LL log_x(LL a,LL b,LL p)

{

map<LL,int>x;

LL z=(LL)ceil(sqrt(p*1.0));

LL v=Inv(quick_mod(a,z,p),p);

LL e=1;

x[1]=0;

for(int i=1;i<z;i++)

{

e=multi(e,a,p);

if(!x.count(e))

x[e]=i;

}

for(int i=0;i<z;i++)

{

if(x.count(b))

return i*z+x[b];

b=multi(b,v,p);

}

return -1;

} LL sol[1005]; void Solve(LL a,LL b,LL n)

{

LL d,x,y;

d=extend_Euclid(a,n,x,y);

if(b%d) puts("-1");

else

{

n/=d;b/=d;

sol[0]=(x*b%n+n)%n;

for(int i=1;i<d;i++)

sol[i]=sol[i-1]+n;

for(int i=0;i<d;i++)

sol[i]=quick_mod(g,sol[i],m);

sort(sol,sol+d);

for(int i=0;i<d;i++)

cout<<sol[i]<<endl;

}

} int main()

{

int t=1;

isprime();

while(cin>>k>>m>>newx)

{

find();

LL t1=log_x(g,newx,m);

LL t2=m-1;

cout<<"case"<<t++<<":"<<endl;

Solve(k,t1,t2);

}

return 0;

}

## HDU3930( Discrete logarithm and primitive root ) More articles about

- Primordial root & A simple summary of discrete logarithm
Primordial root & discrete logarithm 1. Primordial root 1. Definition : Definition \(Ord_m(a)\) In order to make \(a^d\equiv1\;(mod\;m)\) The smallest established d( among a and m Coprime ) According to Euler's Theorem : \(Ord\le\P ...

- Remain true to our original aspiration , Party must always ——NOIP2016 Feeling before
Remain true to our original aspiration , Party must always The bell rings in the garden , All things are changeable . The two Saro trees lose their color , Prosperity turns to decline like vicissitudes . Pride never lasts , It's like a dream in spring . The fierce will be destroyed , Like dust before the wind . —— . I'm afraid the most frightening thing in life is to choose , Now you have ...

- number theory day1 —— Basic knowledge of （ People ）
[pixiv] https://www.pixiv.net/member_illust.php?mode=medium&illust_id=61632537 Xiang Da (hei) Guy (e) Power Science (di ...

- HDU3930 （ Primordial root ）
Given the equation X^A = B (mol C) , seek stay [0,C) All the solutions in , also C Prime number . set up rt by C The original root , be X = rt^x ( This is equivalent to asking for A^x =B (mol C) Use big ...

- BZOJ 3992: [SDOI2015] Sequence statistics [ Fast number theory transformation Generating function discrete logarithm ]
3992: [SDOI2015] Sequence statistics Time Limit: 30 Sec Memory Limit: 128 MBSubmit: 1017 Solved: 466[Submit][Statu ...

- Proof and calculation (2): Discrete logarithm problem (Discrete logarithm Problem, DLP)
Discrete logarithm problem , English is Discrete logarithm Problem, Sometimes it's short for Discrete log, The problem is more than ten open mathematical problems (Open Problems in Mathematics, ...

- BZOJ.3992.[SDOI2015] Sequence statistics (DP NTT Primordial root )
Topic link \(Description\) Given \(n,m,x\) And collection \(S\). seek \(\prod_{i=1}^na_i\equiv x\ (mod\ m)\) Number of alternatives . among \(a_i\in S\). ...

- 【 number theory 】【 Primordial root 】【 Dynamic programming 】【bitset】2017 Sichuan provincial competition K.2017 Revenge
The question : Here you are. n( No more than 200w) Number , And a number r, How many options do you have , So that you can take out a subset , We can make the product of them mod 2017 be equal to r. 2017 Yes 5 This root , You can use discrete logarithm ( indicators ) The idea of transformation from multiplication to addition ...

- UOJ #86 mx The combination number of ( digit DP+NTT+ Primitive root optimization )
Subject portal matthew99 Shen Zhen's explanation is very clear , Kneeling rotten Orzzzzzzzzzzzzz To sum up , There are many important breakthroughs in this topic 1.Lucas Theorem notice n,m It's very big, but the modulus is very small , Easy to think of $lucas ...

## Random recommendation

- Leetcode: Sort Characters By Frequency
Given a string, sort it in decreasing order based on the frequency of characters. Example 1: Input: ...

- Mongo For embedded documents CRUD
{ "_id" : ObjectId("5706032acd0a6194868cf53e"), "list" : { "age&q ...

- Maven Build Life Cycle--reference
What is Build Lifecycle? A Build Lifecycle is a well defined sequence of phases which define the ord ...

- Android Call the system address book
There are three steps to this process :1) License to your app's manifest Add permission to read address book data in <uses-permission android:name="android.permission ...

- HDU1425 <sort Quick line up >
Here you are. n It's an integer , Please output the first... In the order from big to small m Large number . Each group of test data has two lines , The first line has two numbers n,m(0<n,m<1000000), The second line contains n Each is different , And they're all in the range [-500000,5000 ...

- Vulkan Tutorial 18 Restructuring the exchange chain
operating system :Windows8.1 The graphics card :Nivida GTX965M development tool :Visual Studio 2017 Introduction Now we've successfully drawn triangles on the screen , But in some cases , ...

- PAT (Basic Level) Practice （ chinese ）1002 Write this number （20 branch )
Topic link :https://pintia.cn/problem-sets/994805260223102976/problems/994805324509200384 #include <iost ...

- pyhon---- The relationship between functions and methods
1. If you call with a class name , For the function , It needs to be transmitted manually self 2. If you use object calls , For the way , No manual transmission self class Foo(object): def __init__(self): self.name=& ...

- ABAP-Generate dynpro Dynamic screen
1. Get screen parameter values FUN: RS_SCRP_GET_SCREEN_INFOS call function 'RS_SCRP_GET_SCREEN_INFOS' exporting dynnr = ' ...

- sql Inquire about job
use msdb go --if object_id('tempdb..#SqlAgentJob') is not null -- drop table #SqlAgentJob --go decla ...