subject ：Broot

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,b;
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=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;
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=(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

1. Primordial root &amp; 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 ... 2. 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 ... 3. 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 ... 4. 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 ... 5. 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 ... 6. 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, ... 7. 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$$. ...

8. 【 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 ...

9. 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

1. Leetcode: Sort Characters By Frequency

Given a string, sort it in decreasing order based on the frequency of characters. Example 1: Input: ...

2. Mongo For embedded documents CRUD

{ "_id" : ObjectId("5706032acd0a6194868cf53e"), "list" : { "age&q ...

3. Maven Build Life Cycle--reference

What is Build Lifecycle? A Build Lifecycle is a well defined sequence of phases which define the ord ...

4. Android Call the system address book

5. HDU1425 &lt;sort Quick line up &gt;

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 ...

6. 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 , ...

7. PAT (Basic Level) Practice （ chinese ）1002 Write this number （20 branch )

Topic link :https://pintia.cn/problem-sets/994805260223102976/problems/994805324509200384 #include <iost ...

8. 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=& ...

9. 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 = ' ...