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

  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

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

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

  10. sql Inquire about job

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