第一题：fibo矩阵快速幂
无压力，给信心的
type matrix=array[1..2,1..2] of qword; var c,cc:matrix; t,bili:longint; n,p:int64; function multiply(x,y:matrix):matrix; var temp:matrix; begin temp[1,1]:=(x[1,1]*y[1,1]+x[1,2]*y[2,1]) mod p; temp[1,2]:=(x[1,1]*y[1,2]+x[1,2]*y[2,2]) mod p; temp[2,1]:=(x[2,1]*y[1,1]+x[2,2]*y[2,1]) mod p; temp[2,2]:=(x[2,1]*y[1,2]+x[2,2]*y[2,2]) mod p; exit(temp); end; function getcc(n:int64):matrix; var temp:matrix; t:int64; begin if n=1 then exit(c); t:=n div 2; temp:=getcc(t); temp:=multiply(temp,temp); if odd(n) then exit(multiply(temp,c)) else exit(temp); end; procedure init; begin readln(n,p); c[1,1]:=1; c[1,2]:=1; c[2,1]:=1; c[2,2]:=0; if n=0 then begin writeln(0); exit; end; if n=1 then begin writeln(1 mod p); exit; end; if n=2 then begin writeln(1 mod p); exit; end; cc:=getcc(n-2); end; procedure work; begin writeln((cc[1,1]+cc[1,2]) mod p); end; begin assign(input,'eins.in'); reset(input); assign(output,'eins.out'); rewrite(output); readln(t); for bili:=1 to t do begin init; if (n>2) then work; end; close(input); close(output); end.
第二题：树状数组
把求和变成求xor，剩下模板，再给信心
var a,f:array[0..200010] of longint; l,r,x,y,z,m,n,i,j:longint; function lowbit(x:longint):longint; begin exit(x and (-x)); end; procedure build(pos,x:longint); var i:longint; begin i:=pos; while i<=n do begin f[i]:=f[i] xor x; inc(i,lowbit(i)); end; end; function sum(x:longint):longint; var tail,s:longint; begin tail:=x; s:=0; while tail>0 do begin s:=s xor f[tail]; dec(tail,lowbit(tail)); end; sum:=s; end; procedure change(x,y:longint); var p:longint; begin p:=x; while p<=n do begin f[p]:=f[p] xor a[x] xor y; inc(p,Lowbit(p)); end; a[x]:=y; end; begin assign(input,'zwei.in'); reset(input); assign(output,'zwei.out'); rewrite(output); readln(n,m); for i:=1 to n do begin read(a[i]); build(i,a[i]); end; for i:=1 to m do begin read(z,x,y); if z=0 then change(x,y); if z=1 then writeln(sum(y) xor sum(x-1)); end; close(input); close(output); end.
第三题：
欧拉函数，写了好几次才过，后来发现快速幂写错了（捂脸= =）
var i,t,n,mo,ans,k:int64; bilibili:longint; function gcd(x,y:int64):int64; begin if y=0 then exit(x); exit(gcd(y,x mod y)); end; function phi(k:int64):int64; var i,ret:int64; begin ret:=1; i:=2; while i*i<=k do begin if k mod i=0 then begin ret:=ret*(i-1); k:=k div i; while k mod i=0 do begin ret:=ret*i; k:=k div i; end; end; inc(i); end; if k>1 then ret:=ret*(k-1); exit(ret); end; function pow(a,b:int64):int64; var ret,i:int64; begin ret:=1; while b<>0 do begin if b and 1<>0 then begin ret:=(ret*a) mod mo; end; a:=(a*a) mod mo; b:=b>>1; end; exit(ret mod mo); end; begin assign(input,'drei.in'); reset(input); assign(output,'drei.out'); rewrite(output); readln(t); for bilibili:=1 to t do begin readln(n,mo); if mo=1 then begin writeln(-1); continue; end; if n=0 then begin writeln(-1); continue; end; if n=1 then begin writeln(1); continue; end; if gcd(n,mo)>1 then begin writeln(-1); continue; end; ans:=phi(mo); k:=ans; i:=2; while i*i<=k do begin if k mod i=0 then begin if (pow(n,i)=1) and (i<ans) then ans:=i; if (pow(n,k div i)=1) and (k div i<ans) then ans:=k div i; end; inc(i); end; writeln(ans); end; close(input); close(output); end.
喜欢就收藏一下，vic私人qq：1064864324，加我一起讨论问题，一起进步^-^