鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 网站安全 > 加密解密 > >

1712: [Usaco2007 China]Summing Sums 加密

来源:互联网 作者:佚名 时间:2015-09-03 09:27
题解:其实直接根据原来的题意手推一下,不难发现规律,其实这个主要就是由一个等比数列的和构成的,别的不难,推推即可 我。。居然把取模的数一开始当成987654321了,结果还费了半天劲去求phi,还WA掉了TT,后来发现题目中的98765431原来就是个素数TT,别的

 

题解:其实直接根据原来的题意手推一下,不难发现规律,其实这个主要就是由一个等比数列的和构成的,别的不难,推推即可

我。。居然把取模的数一开始当成987654321了,结果还费了半天劲去求phi,还WA掉了TT,后来发现题目中的98765431原来就是个素数TT,别的真的没了,感觉切忌考场上再次逗比TT

 1 const p=98765431;
 2 var
 3    i,j,k,l,m,n:longint;
 4    sum,a1,a2,a3,a4:int64;
 5    a:array[0..1000000] of int64;
 6 function ksm(x,y:int64):int64;
 7          var z:int64;
 8          begin
 9               if y=0 then exit(1);
10               if y=1 then exit(x mod p);
11               z:=ksm(x,y div 2) mod p;
12               z:=(z*z) mod p;
13               if odd(y) then z:=(z*x) mod p;
14               exit(z);
15          end;
16 function trans(x:int64):int64;
17          begin
18               if x>=0 then exit(x mod p);
19               x:=(x+(abs(x) div p+1)*p) mod p;
20               exit(x);
21          end;
22 begin
23      readln(n,m);
24      for i:=1 to n do readln(a[i]);
25      sum:=0;
26      for i:=1 to n do
27          begin
28               a[i]:=a[i] mod p;
29               sum:=(sum+a[i]) mod p;
30          end;
31      a1:=(1-ksm(1-n,m));
32      a1:=((sum*a1) mod p);
33      a1:=(ksm(n,p-2)*a1) mod p;
34      a2:=ksm(-1,m+1);
35      for i:=1 to n do writeln(trans(a2*(a1-a[i])));
36      readln;
37 end.     

 

网友评论
<