C++(g++ 7.5.0) 解法, 执行用时: 24ms, 内存消耗: 2408K, 提交时间: 2022-10-24 17:47:01

#include <bits/stdc++.h>
#define IOS   ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define xs(a) cout<<setiosflags(ios::fixed)<<setprecision(a);
#define FOR(i, a, b) for (ll (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (ll (i) = (a); (i) >= (b); (i)--)
using namespace std;
#define ull unsigned long long
#define ll long long
typedef pair<ll,ll> pll;
const int N=1e6+5;
/*-----------------------------------------------------------------------------------------------*/
ll phi;
ll mig;
ll qpow(ll a, ll b,ll mod) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans%mod;
}
vector<ll>fac;
void get_fac(ll x){
	for(ll i=2;i*i<=x;i++){
		if(x%i==0){
			fac.push_back(i);
			while(x%i==0)x/=i;
		}
	}
	if(x>1)fac.push_back(x);
	return ;
}
bool check(ll x){
	for(auto to:fac){
		ll p=phi/to;
		if(qpow(x,p,phi+1)==1)return 0;
	}
	if(qpow(x,phi,phi+1)==1)return 1;
	return 0;
}
ll get_mig(ll p){
	FOR(g,1,p-1){
		if(check(g))return g;
	}
	return 0;
}
vector<ll>ans;
void BSGS(ll a,ll b,ll p){
    if(b==1)ans.push_back(0);
	// (a^x)%p = b%p    
	// ll x* = A*上取整(sqrt[p])-c   c=(0~上取整(sqrt[p]))
	// a^(A*y)=b*a^c  (同余%mod)
	// 解 x = A*y-c   ->  枚举A 
	map<ll,ll>mp;
	ll y=sqrt(p)+1;
	ll base=b;
	FOR(i,0,y){   // 先记录 b*a^c
		mp[base]=i;
		(base*=a)%=p;
	}
	base=qpow(a,y,p);
	ll tmp=1;
	FOR(i,1,y+1){
		tmp=tmp*base%p;
		if(mp.count(tmp))ans.push_back(i*y-mp[tmp]);
	}
}

signed main(){
	ll p,k,a;cin>>p>>k>>a;
    if(!a){
        cout<<1<<endl<<0<<endl;
        return 0;
    }
	phi=p-1;// p 和 k 为质数
	get_fac(phi);//素因子
	mig=get_mig(p);// 求最小的原根
	BSGS(qpow(mig,k,p),a,p);

	for(auto &v:ans){
		v=qpow(mig,v,p);
	}
	sort(ans.begin(),ans.end());
	ans.erase(unique(ans.begin(),ans.end()),ans.end());
	cout<<ans.size()<<endl;
	for(auto to:ans){
		cout<<to<<' ';
	}
	cout<<endl;

	return 0;
}

C++ 解法, 执行用时: 16ms, 内存消耗: 1932K, 提交时间: 2022-04-08 18:46:02

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p,k,a,x;
ll qpow(ll a,ll k,ll p){ll res=1;while(k){if(k&1)res=res*a%p;a=a*a%p;k>>=1;}return res;}
ll get_rt(ll x)
{
    vector<ll> pri;
    ll phi=x-1;
    for(ll i=2;i*i<=phi;i++)
    {
        if(!(phi%i))
        {
            while(!(phi%x))phi/=x;
            pri.push_back(i);
        }
    }
    if(phi>1)pri.push_back(phi);
    phi=x-1;
    for(ll i=1;i<x;i++)
    {
        bool flag=true;
        for(auto t:pri)
        {
            if(qpow(i,phi/t,p)==1){flag=false;break;}
        }
        if(flag)return i;
    }
    return 0;
}
ll BSGS(ll a,ll b,ll p)
{
    if(1%p==b%p)return 0;
    ll A=sqrt(p)+1;
    unordered_map<ll,ll> mp;
    ll t=b%p;
    for(ll B=0;B<A;B++)
    {mp[t]=B;t=t*a%p;}
    a=qpow(a,A,p);
    for(ll i=1,j=a;i<=A;i++)
    {
        if(mp.count(j))return i*A-mp[j];
        j=j*a%p;
    }
//     return -1;
    printf("no solution");
    exit(0);
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0){x=1;y=0;return a;}
    ll d=exgcd(b,a%b,x,y);
    ll t=y;
    y=x-a/b*y;x=t;return d;
}
vector<ll>res;
int main()
{
    scanf("%lld%lld%lld",&p,&k,&a);
    if(!a){cout<<"1\n0\n";return 0;}
    ll g=get_rt(p);
    ll c=BSGS(g,a,p),x,y;
    ll t=exgcd(k,p-1,x,y);
    if(c%t){printf("0");return 0;}
    y=(p-1)/t;
    x=(x%y+y)%y;c=x*(c/t)%y;
    while(c<(p-1))
    {
        res.push_back(qpow(g,c,p));c+=y;
    }
    sort(res.begin(),res.end());
//     cout<<g<<endl;
    cout<<res.size()<<'\n';
    for(auto x:res)cout<<x<<" ";
}