Eva

Limit: 5 Sec  Memory Limit: 64 MB

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。

/**************************************************************

    Problem: 1408

    User: ictsing

    Language: C++

    Result: Accepted

    Time:8 ms

    Memory:1288 kb

****************************************************************/

 

//1408: [Noi2002]Robot

/*

题目好长哇Qwq

政客目前为止有偶数个奇质因子的欧拉函数的前缀和

军人目前为止有奇数个奇质因子的欧拉函数的前缀和

学者可以由m-1减去前两种，减1为去掉1

注意二是特殊的。。。

 

φ(a*p)=φ(a)*φ(p)=φ(a)*(p-1)(p为质数且(a,p)=1)

对第i个质因数p操作,如果不取，那么总和为ans1,否则为ans2*(p-1)

*/

#include <iostream>

#include <cstdio>

using namespace std;

const int mod=10000;

int quickpow(int a,int b)

{

    int res=1;

    while(b)

    {

        if(b&1) res=res*a%mod;

        a=a*a%mod,b>>=1;

    }

    return res;

}

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

int main()

{

    int k=read();

    int ans1=1,n=1,ans2=0;

    for(int i=1;i<=k;i++)

    {

        int x=read(),y=read();

        n=n*quickpow(x,y)%mod;

        if(x==2) continue;

        int a=(ans1+ans2*(x-1))%mod;

        int b=(ans2+ans1*(x-1))%mod;

        ans1=a,ans2=b;

    }

    int ans3=(n-ans1-ans2+mod+mod)%mod;

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

    return 0;

}