首页 > 代码库 > NOI2002robot

NOI2002robot

2024-07-07 23:02:24   227人阅读

这题又是纯数论题……

独立数就是欧拉函数，政客和军人的含义已经说的很清楚了，学者是最多的……

首先，如果我们知道了政客和军人的答案，那就只要用n的所有因子的欧拉函数值减去这两个值，然后取模就行了。

但一个数的因子有很多，而且题目中给的数据范围又颇大，所以我们想肯定有什么方法可以快速推出一个数的所有因子的欧拉函数值之和。

经过思考，我们有如下结论：

因为对于一个素数来说，phi（p的n次方）=p的（n-1）次方*（p-1）

这是因为这些式子拆开之后每一项都对应着一个因子的欧拉函数值，不重不漏。

接下来考虑，如何计算政客和军人

其实我在数学竞赛书上看过这一题……（给定一个集合及其中的所有元素，求它的所有奇子集的元素乘积之和和偶子集的元素乘积之和……）

其实这和上面的方法类似

设偶子集之和为A，奇子集之和为B。

（在此题中认为1既不是政客也不是军人）

S1=（1+X1）*（1+X2）*（1+X3）……（1+Xn）-1

展开之后每一项都对应一个子集乘积，所以A+B=S1

S2=（1-X1）*（1-X2）*（1-X3）……（1+Xn）-1

展开之后奇子集乘积符号为负，偶子集符号为正。所以A-B=S2

所以A=（S1+S2）除以2

       B=S1-A

但需要注意的是，因为要对答案取模，所在计算过程中直接mod10000是不够的，因为涉及了除法。所以要多保留一位，在计算过程中mod100000，最后输出mod10000

至于为何，请读者仔细思考。

至此，此题完美解决。

代码：（在wikioi上AC，在bzoj上WA，奇了怪了……）‘

 1 var ans1,ans2,ans3,p,e,n,t:int64;
 2     i:longint;
 3 function mo(x:int64):longint;
 4  begin
 5  mo:=((x mod 100000)+100000) mod 100000;
 6  end;
 7 function power(num,times:longint):longint;
 8  var tmp:longint;
 9  begin
10  if times=1 then exit(mo(num));
11  tmp:=power(num,times>>1);
12  power:=mo(tmp*tmp);
13  if times and 1=1 then power:=mo(power*num);
14  end;
15 procedure main;
16  begin
17  readln(n);
18  ans1:=1;ans2:=1;ans3:=1;
19  for i:=1 to n do
20   begin
21   readln(p,e);
22   ans3:=mo(ans3*power(p,e));
23   if p=2 then continue;
24   ans1:=mo(ans1*(1+p-1));
25   ans2:=mo(ans2*(1-p+1));
26   end;
27  if n=1 then
28   begin
29   ans1:=0;
30   if p<>2 then ans2:=p-1 else ans2:=0;
31   ans3:=mo(ans3-1-ans1-ans2);
32   exit;
33   end;
34  ans1:=mo(ans1-1);ans2:=mo(ans2-1);ans3:=mo(ans3-1);
35  t:=ans1;ans1:=mo(ans1+ans2)>>1;ans2:=mo(t-ans1);ans3:=mo(ans3-ans1-ans2);
36  end;
37 procedure print;
38  begin
39  writeln(ans1 mod 10000);
40  writeln(ans2 mod 10000);
41  writeln(ans3 mod 10000);
42  end;
43 begin
44  main;
45  print;
46 end.
View Code

 

 


联系
我们