51nod1039 x^3 mod p
2024-10-19 03:26:22
X*X*X mod P = A,其中P为质数。给出P和A,求<=P的所有X。
Input
第1行:一个数T,表示后面用作输入测试的数的数量。(1 <= T <= 1000)
第2 - T + 1行:每行两个数P A,中间用空格隔开。(1 <= A < P <= 10^9, P为质数)
Output
共T行,每行包括符合条件的X,且0 <= X <= P,如果有多个,按照升序排列,中间用空格隔开。如果没有符合条件的X,输出:No Solution
首先求P的原根g
bsgs求出b满足gb=A (mod P)
所以X3=gb+k(P-1)=A (mod P)
X=g(b+k(P-1))/3 ( (b+k(P-1))|3 , k∈{0,1,2} )
(别问我为什么不是c++,以上非正解是卡过去的
import java.util.*;
public class Main{
static final int N=32007;
static boolean np[]=new boolean[N+4];
static int ps[]=new int[N/5],pp=0;
static final int P=65536,A=2939;
static int xs[]=new int[P],ys[]=new int[P],ts[]=new int[P],now=1;
static int as[]=new int[16],ap=0;
static int pow(int x,int n,int p){
int v=1;
for(;n!=0;n>>=1){
if((n&1)!=0)v=(int)((long)v*x%p);
x=(int)((long)x*x%p);
}
return v;
}
static int inv(int x,int p){
return pow(x,p-2,p);
}
static void get_primes(){
for(int i=2;i<=N;i++){
if(!np[i])ps[pp++]=i;
for(int j=0;j<pp&&i*ps[j]<=N;j++){
np[i*ps[j]]=true;
if(i%ps[j]==0)break;
}
}
}
static int root(int x){
int fs[]=new int[32],fp=0,x0=x-1;
for(int i=0,w;i<pp;i++){
w=ps[i];
if(w*w>x0)break;
if(x0%w==0){
fs[fp++]=w;
do x0/=w;while(x0%w==0);
}
}
if(x0!=1)fs[fp++]=x0;
x0=x-1;
for(int i=2;i<x;i++){
boolean is=true;
for(int j=0;j<fp;j++)if(pow(i,x0/fs[j],x)==1){
is=false;
break;
}
if(is)return i;
}
return -1;
}
static void clear(){
++now;
}
static void ins(int x,int y){
int w=x&65535;
while(ts[w]==now)w=w+A&65535;
xs[w]=x;
ys[w]=y;
ts[w]=now;
}
static int find(int x){
int w=x&65535;
while(ts[w]==now){
if(xs[w]==x)return ys[w];
w=w+A&65535;
}
return -1;
}
static int bsgs(int a,int b,int p){
int r=(int)(Math.sqrt(p)*0.7),_a=inv(a,p);
clear();
for(int i=0,x=b;i<r;i++,x=(int)((long)x*_a%p))ins(x,i);
for(int i=r,_x=pow(a,r,p),x=_x;;i+=r,x=(int)((long)x*_x%p)){
int v=find(x);
if(v!=-1)return i+v;
}
}
public static void main(String[] args){
get_primes();
Scanner sc=new Scanner(System.in);
int T,p,a;
for(T=sc.nextInt();T>0;T--){
p=sc.nextInt();a=sc.nextInt();
if(p<400){
ap=0;
for(int i=1;i<p;i++)if(i*i*i%p==a)as[ap++]=i;
}else{
int g=root(p);
int m=bsgs(g,a,p);
ap=0;
for(int i=0;i<3;i++){
long v=m+i*(long)(p-1);
if(v%3==0)as[ap++]=pow(g,(int)(v/3),p);
}
for(int aa=0;aa<ap;aa++)
for(int b=1;b<ap;b++)if(as[b-1]>as[b]){
int x=as[b];
as[b]=as[b-1];
as[b-1]=x;
}
}
if(ap>0){
for(int i=0;i<ap-1;i++)System.out.print(as[i]+" ");
System.out.println(as[ap-1]+"");
}else System.out.println("No Solution");
}
}
}
最新文章
- ASP.NET提取多层嵌套json数据的方法
- uboot的编译
- Initializing connection provider: org.springframework.orm.hibernate3.LocalDataSourceConnectionProvider停住了
- psql 命令行使用
- c中的关键字、标识符、注释
- 16位的MD5加密和32位MD5加密的区别
- ADO访问Access数据库错误解决心得随笔
- js学习--DOM操作详解大全二(window对象)
- 【前端】react学习阶段总结,学习react、react-router与redux的这些事儿
- 极化码之tal-vardy算法(2)
- IDirectDraw接口
- mysql5.7连接不上可能的问题(针对新安装的mysql5.7可能出现的问题)
- js之promise讲解
- vue设置路由跳转参数,以及接收参数
- PDF to image
- python return 返回多个值
- mapreduce的输入格式 --- InputFormat
- error: In function ‘void* opencv_showimg(void*)’:
- celery初始化
- Struts2 01---环境搭配
热门文章
- java中byte数据转换为c#的byte数据
- jQuery关于Select的操作
- Linux下软件包的多种安装方式
- This application failed to start because it could not find or load the Qt platform plugin “windows”错误解决方法
- CSS 阴影怎么写?
- 故障模块名称: mso.dll
- LeetCode() Valid Anagram 有问题!!!
- android中ImageView讲解
- 带百分号的数据转json
- 越狱Season 1-Season 1, Episode 3: Cell Test