当前位置:编程学习 > C/C++ >>

SGU 261 Discrete Roots

给定p,k,a,其中p,k是素数,求x^k=a (mod p)。
传说中的much 易做图r task。。。。
 
设r是p的原根,(素数都有原根)
那么r^1,r^2...r^phi(p)构成模p的完全剩余系,
故可设x=r^i ,a=r^j,那么等式化成
r^(i*k)=r^j (mod p)
那么由定理可得 i*k=j (mod p-1)
由r^j=a mod p 可由离散对数求得j
由i*k=j mod p-1 可由模线性方程求得i
由x=r^i 求得x
然后对所有x取余后排序,输出即可。
 
[cpp]  
#include<map>  
#include<cstdio>  
#include<cmath>  
#include<vector>  
#include<iostream>  
#include<algorithm>  
using namespace std;  
typedef long long ll;  
vector<ll>f,as;  
ll pow(ll a,ll b,ll mod){  
    ll as=1;  
    while(b){  
        if(b&1)as=(as*a)%mod;  
        a=(a*a)%mod;b>>=1;  
    }  
    return as;  
}  
bool g_test(ll g,ll p){  
    for(ll i=0;i<f.size();i++)  
        if(pow(g,(p-1)/f[i],p)==1)  
            return 0;  
    return 1;  
}  
ll yuangen(ll p){  
    f.clear();  
    ll tmp=p-1;  
    for(ll i=2;i<=tmp/i;i++)  
        if(tmp%i==0){  
            f.push_back(i);  
            while(tmp%i==0)  
                tmp/=i;  
        }  
    if(tmp!=1)f.push_back(tmp);  
    ll g=0;  
    while(++g)  
        if(g_test(g,p))  
            return g;  
}  
ll discrete_log(ll x,ll n,ll m){//x^y=n (mod m) 求 y  
    map<ll,int>rec;  
    ll s=(ll)(sqrt(m)+0.5);  
    ll cur=1;  
    for(int i=0;i<s;i++){  
        rec[cur]=i;  
        cur=cur*x%m;  
    }  
    ll mul=cur;  
    cur=1;  
    for(int i=0;i<s;i++){  
        ll more=n*pow(cur,m-2,m)%m;  
        if(rec.count(more))return i*s+rec[more];  
        cur=cur*mul%m;  
    }  
    return -1;  
}  
ll ex_易做图(ll a,ll b,ll& x,ll& y){  
    if(b==0){  
        x=1;y=0;  
        return a;  
    }  
    else{  
        ll r=ex_易做图(b,a%b,y,x);  
        y-=x*(a/b);  
        return r;  
    }  
}  
void line_mod_equation(ll a,ll b,ll n){//ax=b (mod n) 求x  
    ll x,y,d;as.clear();  
    d=ex_易做图(a,n,x,y);  
    if(b%d==0){  
        x%=n;x+=n;x%=n;  
        as.push_back(x*(b/d)%(n/d));  
        for(ll i=1;i<d;i++)  
            as.push_back((as[0]+i*n/d)%n);  
    }  
}  
int main(){  
    ll a,k,p,g,q;  
    while(~scanf("%lld%lld%lld",&p,&k,&a)){  
        if(a==0){puts("1\n0");continue;}//a==0特判  
        g=yuangen(p);  
        q=discrete_log(g,a,p);  
        line_mod_equation(k,q,p-1);  
        for(int i=0;i<as.size();i++)  
            as[i]=pow(g,as[i],p);  
        sort(as.begin(),as.end());  
        printf("%d\n",as.size());  
        for(int i=0;i<as.size();i++)  
            printf("%lld%c",as[i],i==as.size()-1?'\n':' ');  
    }  
    return 0;  
}  
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,