Processing math: 66%
BZOJ2346: [Baltic 2011]Lamp
BZOJ1061: [Noi2008]志愿者招募 线性规划之--构造初始可行解

BZOJ1420: Discrete Root && BZOJ1319

shinbokuow posted @ 10 年前 in BZOJ with tags 数学 原根 , 1342 阅读

 

题解:

事实上p是质数...

所以我们先求出原根g.

然后对于两边取指标,就得到ind(x)\times{k}\equiv{ind(a)}\pmod{p-1}

这就可以直接用拓展欧几里得算法求解了.

至于拓展欧几里得的一些细节见代码吧...

代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include<cmath>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
  
typedef long long ll;
  
ll pow(ll x,ll y,ll p){
    ll re=1,t=x;
    for(;y;y>>=1,t=t*t%p)
        if(y&1)
            re=re*t%p;
    return re;
}
  
inline void exgcd(ll a,ll b,ll&d,ll&x,ll&y){
    if(!b){
        d=a;
        x=1;
        y=0;
    }
    else{
        exgcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}
  
struct Hashset{
    static const int mod=1313131;
    int head[mod],next[30010],f[30010],v[30010],ind;
    inline void reset(){
        memset(head,-1,sizeof head);
        ind=0;
    }
    inline int operator[](int x){
        int ins=x%mod;
        for(int j=head[ins];j!=-1;j=next[j])
            if(f[j]==x)
                return v[j];
        return -1;
    }
    inline void insert(int x,int _v){
        int ins=x%mod;
        for(int j=head[ins];j!=-1;j=next[j])
            if(f[j]==x){
                v[j]=min(v[j],_v);
                return;
            }
        f[ind]=x;
        v[ind]=_v;
        next[ind]=head[ins];
        head[ins]=ind++;
    }
}M;
  
inline ll BSGS(ll a,ll b,ll p){
    ll m=ceil(sqrt(p)),i,j,t;
    M.reset();
    for(t=1,i=0;i<m;++i,(t*=a)%=p)
        M.insert(t,i);
    ll rev=pow(t,p-2,p);
    for(i=0;i*m<p;++i,(b*=rev)%=p)
        if(M[b]!=-1)
            return i*m+M[b];
    return -1;
}
  
inline ll get_g(ll p){
    static int pr[110];
    int num=0;
    ll t=p-1;
    for(int i=2;i*i<=p;++i){
        if(t%i==0){
            pr[++num]=i;
            while(t%i==0)
                t/=i;
        }
    }
    if(t!=1)
        pr[++num]=t;
    for(int i=1;;++i){
        bool ok=1;
        for(int j=1;j<=num;++j)
            if(pow(i,(p-1)/pr[j],p)==1){
                ok=0;
                break;
            }
        if(ok)
            return i;
    }
}
  
inline ll gcd(ll a,ll b){
    return(!b)?a:gcd(b,a%b);
}
  
#define pb push_back
vector<ll>ans;
  
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
#endif
    ll p,k,a,i,j;
    cin>>p>>k>>a;
    ll g=get_g(p);
    if(a==0)
        printf("1\n0");
    else{
        ll ind_a=BSGS(g,a,p);
        if(ind_a%gcd(k,p-1))
            puts("0");
        else{
            ll temp=(p-1)/gcd(k,p-1);
            ll d,x,y;
            exgcd(k,p-1,d,x,y);
            x=(x%temp+temp)%temp;
            ind_a/=gcd(k,p-1);
            (x*=ind_a)%=temp;
            while(x<p){
                ans.pb(pow(g,x,p));
                x+=temp;
            }
            sort(ans.begin(),ans.end());
            for(printf("%d\n",ans.size()),i=0;i<ans.size();++i)
                printf("%lld\n",ans[i]);
        }
    }
    return 0;
}
Small_feed 评论 (1)
1
[回复]
charlly 说:
3 年前

The best forum to turn to for information on various programmes is this one. You will have no trouble finding programmes here, and I think it buy cheap diamond rings would be beneficial for you to participate. Thank you so much for having me here.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter