NC232625. X^A Mod P
描述
输入描述
第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 100)
第2 - T + 1行：每行3个数P A B，中间用空格隔开。(1 <= A, B < P <= 10^9, P为质数)
输出描述
共T行，每行包括符合条件的X，且0 <= X < P，如果有多个，按照升序排列，中间用空格隔开。如果没有符合条件的X，输出：No Solution。所有数据中，解的数量不超过Sqrt(P)。
示例1
输入:
3 11 3 5 13 3 1 13 2 2
输出:
3 1 3 9 No Solution
C++(g++ 7.5.0) 解法, 执行用时: 303ms, 内存消耗: 2004K, 提交时间: 2022-09-07 21:24:40
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline bool read(T&x){
x=0;char c=getchar();int f=1;while(!isdigit(c)&&(c!='-')&&(c!=EOF))c=getchar();
if(c==EOF)return 0;if(c=='-')f=-1,c=getchar();
while(isdigit(c)){x=x*10+(c&15);c=getchar();}x*=f;return 1;
}template<typename T,typename...Args>inline bool read(T&x,Args&...args){bool res=1;res&=read(x);res&=read(args...);return res;}
typedef long long LL;typedef unsigned long long u64;typedef unsigned u32;typedef long double LD;typedef pair<int,int> pii;typedef pair<LL,LL> pll;
#define pln putchar('\n')
#define For(i,a,b) for(int i=(a),(i##i)=(b);i<=(i##i);++i)
#define Fodn(i,a,b) for(int i=(a),(i##i)=(b);i>=(i##i);--i)
const int M=1000000007,INF=0x3f3f3f3f;const long long INFLL=0x3f3f3f3f3f3f3f3fLL;
const int N=1000009;
inline LL mul(LL a, LL b, LL m) {u64 r=(u64)a*b-(u64)((LD)a/m*b+0.5L)*m;return r<m?r:r+m;}
inline LL fp(LL a,LL b,LL Mod){LL res=(Mod!=1);for(;b;b>>=1,a=a*a%Mod)if(b&1)res=res*a%Mod;return res;}
inline LL fpl(LL a,LL b,LL Mod){LL res=(Mod!=1);for(;b;b>>=1,a=mul(a,a,Mod))if(b&1)res=mul(res,a,Mod);return res;}
template<typename T>inline T gcd(T a,T b){while(b){T t=b;b=a%b;a=t;}return a;}template<typename T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
template<typename T>inline void exgcd(T a,T b,T&x,T&y,T&d){if(b==0){x=1,y=0,d=a;}else{exgcd(b,a%b,y,x,d);y-=(a/b)*x;}}
inline bool crt(pll&a,pll b)/*注意检查参数是否合法 求非负解还是正解*/{LL g,u,d;exgcd(a.second,b.second,u,d,g);d=b.first-a.first;if(d%g)return 0;
const LL t=b.second/g;a.first+=mul(u,d/g,t)*a.second;a.second*=t;a.first%=a.second;(a.first<0)&&(a.first+=a.second);return 1;}
/*求a(mod p)的逆元 要保证a⊥p*/template<typename T>inline T getinv(T a,T p){T m=0,n=1,x=1,y=0,b=p;while(b)
{const T q=a/b;tie(x,m)=make_tuple(m,x-q*m);tie(y,n)=make_tuple(n,y-q*n);tie(a,b)=make_tuple(b,a-q*b);}(x<0)&&(x+=p);return x;};
LL generator(LL p,bool isprime=1){ //调用前是否确定其为质数
if(p<=3)return p-1;
LL phi=p;
if(!isprime){
LL x=p;
for(LL d=2;d*d<=x;++d)if(x%d==0){
while(x%d==0)x/=d;
phi=phi/d*(d-1);
}
if(x>1)phi=phi/x*(x-1);
}else --phi;
vector<LL>g; // 存 phi 除以其每个质因子的值
if(phi<=3){
g.push_back(1ll);
}else{
LL u=phi;
for(LL d=2;d*d<=u;++d)if(u%d==0){
g.push_back(phi/d);
while(u%d==0)u/=d;
}
if(u>1)g.push_back(phi/u);
}
for(LL q=1;q<p;++q){
if(!isprime&&__gcd(q,p)>1)continue;
bool t=1;
for(int i=0;i<int(g.size());++i)if(fpl(q,g[i],p)==1){
t=0;break;
}
if(t)return q;
}
return -1;
}
struct neal{
static u64 A(u64 x){
x+=0x9e3779b97f4a7c15;
x=(x^(x>>30))*0xbf58476d1ce4e5b9;
x=(x^(x>>27))*0x94d049bb133111eb;
return x^(x>>31);
}
u64 operator()(u64 x)const{
static const u64 C=chrono::steady_clock::now().time_since_epoch().count();
return A(x+C);
}
};//typedef unordered_map<int,int,neal> HASH; //不会被卡
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
typedef __gnu_pbds::gp_hash_table<int,int,neal> HASH;//比较快，但可能被卡
struct{
//快速幂 求逆元 哈希 (__gcd)
int log(int a,int b,int p){//要求(a,p)=1 求最小非负整数x 满足 a^x=b(mod p) 无解返回-1 (不是接口)
if((b-1)%p==0)return 0;
HASH h;const int t=(int)sqrt(p)+1;
for(int j=0;j<t;++j,b=(LL)b*a%p)h[b]=j;
int at=(a=fp(a,t,p));
for(int i=1;i<=t;++i,a=(LL)a*at%p){
auto it=h.find(a);
if(it!=h.end())return i*t-(*it).second;
}return -1;
}
int operator()(int a,int b,int p){//(接口)传入非负整数 a, b 和正整数 p 不要求(a,p)=1
if((b-1)%p==0)return 0;//求正整数解则注释掉
if((b-a)%p==0)return 1;
a%=p;b%=p;
const int _a=a,_b=b,_p=p;
int d=__gcd(a,p),ax=1,t=0;
while(d>1){
if(b%d!=0)break;
b/=d;p/=d;ax=(LL)ax*(a/d)%p;++t;
d=__gcd(a,p);
}
for(int i=2,at=(LL)_a*_a%_p;i<=t;++i,at=(LL)at*_a%_p)if(at==_b)return i;
if(d>1)return -1;
int res=log(a,(LL)b*getinv(ax,p)%p,p);
return res<0?-1:res+t;//求正整数解则要修改
}
}BSGS;
int p,a,b;
inline void solve(int T){
//printf("Case #%d: ",T);
read(p,a,b);
int g=generator(p);
//printf("%d\n",g);exit(0);///
int t=BSGS(g,b,p);
//printf("%d\n",t);exit(0);///
//printf("%d %d %d\n",a,p-1,t);///
int x,y,d;exgcd(a,p-1,x,y,d);
//exit(0);
if(t%d){
puts("No Solution");
return;
}
int v=(p-1)/d;
while(x<0)x+=v;
x=LL(x)*(t/d)%v;
set<int>ans;
while(x<=p-1){
ans.insert(fp(g,x,p));
//break;
x+=v;
}
for(auto it:ans)printf("%d ",it);pln;
}
signed main(){
int t;read(t);
for(int i=1;i<=t;++i)solve(i);
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 436ms, 内存消耗: 2100K, 提交时间: 2022-09-06 09:57:50
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
typedef long long ll;
#define LL ll
#define endl '\n'
ll sb;
ll a,p,g;
vector<ll> fac;
ll ksm(ll a,ll b,ll mod){
ll res=1;
while(b){
if(b&1) res=res*a%mod;
b>>=1;a=a*a%mod;
}
return res;
}
ll BSGS(ll a,ll b,ll p){
if(b==1)return 0;
ll rm=sqrt(p+0.5);
unordered_map<ll,ll>mp;
ll res=b;
for(int i=0;i<rm;++i){
mp[res]=i;
res=res*a%p;
}
a=ksm(a,rm,p);res=a;
for(int i=1;i<=rm;++i){
if(mp.find(res)!=mp.end())return i*rm-mp[res];
res=res*a%p;
}
return -1;
}
void solve(){
cin>>p>>sb>>a;
if(p==2) {
cout<<1<<endl;
return;
}
fac.clear();
ll pp=p-1;
for(int i=2;i*i<=pp;i++){
if(pp%i==0) fac.push_back(i);
while(pp%i==0) pp/=i;
}
if(pp!=1) fac.push_back(pp);
for(ll i=2;i<=p;i++){
if(ksm(i,p-1,p)==1){
bool flag=0;
for(auto v:fac){
if(ksm(i,(p-1)/v,p)==1) flag=1;
}
if(!flag){
g=i;break;
}
}
}
set<ll> s;
ll bb=ksm(g,sb,p);
ll ans=BSGS(bb,a,p);
if(ans==-1||a==0){
cout<<"No Solution"<<endl;
return;
}
ans=ksm(g,ans,p);
s.insert(ans);
ll t=(p-1)/__gcd(sb,p-1);
ll t1=ksm(g,t,p);
for(int i=0;i<sb+3;i++){
ans=ans*t1%p;
if(s.find(ans)!=s.end()) break;
else s.insert(ans);
}
for(auto v:s) cout<<v<<" ";
cout<<endl;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}