[Bzoj2242]常见数值算法

1、给定y,z,p,计算Y^Z Mod P 的值；
2、给定y,z,p，计算满足xy≡ Z ( mod P )的最小非负整数；
3、给定y,z,p，计算满足Y^x ≡ Z ( mod P)的最小非负整数。

• exgcd最后的gcd不需要取模
• 负数的处理 (P+n) mod n
• int64的使用（防止溢出）
(**************************************************************
Problem: 2242
User: HTwood
Language: Pascal
Result: Accepted
Time:636 ms
Memory:2568 kb
****************************************************************)

program math;

Const
maxn=100000;
maxm=2;
StrErr='Orz, I cannot find x!';

Type
rec=record
val,ord:longint;
end;

var
p,q,n,m,op,gcd:int64;
i:longint;
t:array[0..maxn,0..maxm] of rec;

Function safe(P:int64):int64;inline;
begin
exit(((p+n) mod n+n) mod n);
end;

Function times(p,q:int64):int64;//P^Q (mod N)
begin
if q=0 then exit(1);
times:=times(p,q shr 1);
times:=safe(times*times);
if odd(q) then times:=safe(times*p);
end;

Procedure Exgcd(a,b:int64;var x,y:int64);
begin
if b=0 then begin x:=1;y:=0;gcd:=a;exit; end;
Exgcd(b,a mod b,y,x);
y:=safe(y-a div b*x);
end;

Procedure Solve1;inline;//pX+Yn=Q
var
x,y:int64;
begin
Exgcd(p,n,x,y);
if q mod gcd<>0 then begin writeln(StrErr); exit; end;
x:=safe(x);
writeln(safe((q div gcd)*x));
end;

Procedure Addhash(val,ord:int64); inline;
var
hash,i:longint;
begin
hash:=(val mod maxn+maxn) mod maxn;
for i:=1 to maxm do
begin
if t[hash,i].ord>0 then continue;
t[hash,i].ord:=ord;
t[hash,i].val:=val;
break;
end;
end;

Function InHash(P:longint;var pos1,pos2:int64):boolean;inline;
var
hash,i:longint;
begin
hash:=(p mod maxn+maxn) mod maxn;
for i:=1 to maxm do
begin
if t[hash,i].ord=0 then break;
if t[hash,i].val=p then
begin
pos1:=hash;
pos2:=i;
exit(true);
end;
end;
exit(false);
end;

Function inv(P:int64):int64;inline;//pX=1 (mod n)
var
x,y:int64;
begin
Exgcd(p,n,x,y);
if gcd=1 then exit((x+n) mod n) else exit(-1);
end;

Procedure Solve2;inline;//P^x=q (mod n)
var
size,v,now,pos1,pos2:int64;
i:longint;
begin
q:=q mod n;
size:=trunc(sqrt(n))+1;
fillchar(t,sizeof(t),0);
v:=inv(times(p,size));
now:=1;
for i:=1 to size do
begin
now:=(now*p) mod n;
Addhash(now,i);
end;
For i:=0 to size-1 do
begin
if inhash(q,pos1,pos2) then
begin
writeln((size*i+t[pos1,pos2].ord) mod n);
exit;
end;
q:=(q*v) mod n;
end;
Writeln(strErr);
end;

begin
readln(m,op);
for i:=1 to m do
begin
readln(p,q,n);
case op of
1:writeln(times(p,q));
2:solve1;
3:solve2;
end;
end;
end.

posted on 2013-05-30 20:22  灰天飞雁  阅读(721)  评论(0编辑  收藏  举报
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://www.cnblogs.com/htfy/archive/2013/05/30/3108975.html", "fetch_time": 1638349084000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2021-49/segments/1637964359976.94/warc/CC-MAIN-20211201083001-20211201113001-00063.warc.gz", "warc_record_offset": 782659687, "warc_record_length": 8021, "token_count": 922, "char_count": 2371, "score": 3.578125, "int_score": 4, "crawl": "CC-MAIN-2021-49", "snapshot_type": "latest", "language": "en", "language_score": 0.20763373374938965, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00037-of-00064.parquet"}