程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> sgu-261 Discrete Roots

sgu-261 Discrete Roots

編輯：C++入門知識

sgu-261 Discrete Roots

題目大意：

給你兩個質數P和K(2<=P<=109,2<=K<=100000)，還有一個數A(0<=A，求出方程xK=A( mod P)所有的整數解x∈[0,P?1]

解題思路：

首先我們求出P的原根g，然後求出t使得gt=A ( mod P)，這個用大步小步。然後我們令x=gw ( mod P)，那麼有w?K=t ( mod φ(P))，這個用擴展歐幾裡得搞一發就行了。

AC代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include

using namespace std;

long long fact[32000]={0};
long long factp=0;

long long P,K,A;
long long ans[1000010]={0};
long long ansp=0;
map  hash;

long long power(long long a,long long k,long long Mod)
{
    long long o=1;
    for(;k>0;)
    {
        if(k&1) o=a*o%Mod;
        a=a*a%Mod;
        k>>=1;
    }
    return o;
}

long long primitive_root(long long prime)
{
    long long G=0;
    memset(fact,0,sizeof(fact));
    factp=0;
    long long tmp=prime-1;
    for(long long i=2;i*i<=tmp && tmp>2;i++)
    {
        if(tmp%i==0)
        {
            fact[++factp]=i;
            for(;tmp%i==0;) tmp/=i;
        }
    }
    if(tmp!=1) fact[++factp]=tmp;
    for(G=2;G::iterator it;
        it=hash.find(cnt);
        if(it!=hash.end())
            return k*m-it->second;
        cnt=cnt*mult%prime;
    }
    return -1;
}

long long ex_gcd(long long a,long long b,long long & x,long long & y)
{
    if(!b)
    {
        x=1;y=0;
        return a;
    }
    long long nx,ny,d;
    d=ex_gcd(b,a%b,nx,ny);
    x=ny;y=nx-a/b*ny;
    return d;
}


int main()
{
    cin>>P>>K>>A;
    if(A==0) printf("1\n0");
    else if(P==2) cout<<1<<endl<<a<<endl; else="" {="" long="" g="primitive_root(P);" printf("g="%d\n&quot;,G);" dis_log="discrete_logarithm(G,A,P);" if(dis_log="=-1)" cout