BZOJ 1408: [Noi2002]Robot

1408: [Noi2002]Robot

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 510 Solved: 344
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

3
2 1
3 2
5 1

Sample Output

8
6
75

HINT

90号机器人有10个老师，加上它自己共11个。其中政客只有15号；军人有3号和5号；学者有8个，它们的编号分别是：2,6,9,10,18,30,45,90。

Source

分析：

这道题读完题就胜利了...TAT...

其实就是用优(z)美(z)的语言描述了φ函数和μ函数...

需要注意的是φ(1)=0，数互异素数个数的时候不能数2...

ans1和ans2都很好求，因为φ是积性函数，所以我们可以O(n)滴求出...ans3肿么求QAQ...我思考了好久发现自己是zz...所有数的φ之和不就是m么...

减一减就好了...

代码：

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 //by NeighThorn

 using namespace std;

 //大鹏一日同风起，扶摇直上九万里 

 const int maxn=+,Mod=;

 int n,beg,end,ans1,ans2,ans3,p[maxn],e[maxn];

 inline int power(int x,int y){

     int res=;

     while(y){

         if(y&)

             res=res*x%Mod;

         (x*=x)%=Mod,y>>=;

     }

     return res;

 }

 signed main(void){

     scanf("%d",&n);beg=,end=n;

     for(int i=;i<=n;i++)

         scanf("%d%d",&p[i],&e[i]);

     if(p[]==)

         beg++;

     for(int i=beg;i<=end;i++){

         int tmp1=ans1,tmp2=ans2;

         (ans1+=tmp2*(p[i]-)%Mod)%=Mod;

         (ans2+=(tmp1+)*(p[i]-)%Mod)%=Mod;

     }

     ans3=;

     for(int i=;i<=n;i++)

         (ans3*=power(p[i],e[i]))%=Mod;

     ans3=(((ans3-+Mod)%Mod-ans1+Mod)%Mod-ans2+Mod)%Mod;

     printf("%d\n%d\n%d\n",ans1,ans2,ans3);

     return ;

 }//Cap ou pas cap. Cap.

By NeighThorn

秒客网