Description：

给出整数 $m$ 的唯一分解，求所有 $m$ 的约数中 $\mu$ 为 $0/1/-1$ 的欧拉函数和。

$1\leqslant n\leqslant 1000$

Solution：

由于 $\begin{align}\sum_{d|n}\varphi(d)=n\end{align}$ ，所以只用求出 $\mu=1/-1$ 的答案，用 $n$ 减就可以了，考虑增加一个质数 $k$ ，会发现如果选他，选出的数的奇偶性会转换，不选则不用，因此每次把一个答案乘 $(p-1)$ 累加到另一个上即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MOD 10000

int n;

int power(int a,int b)

{

	int res = 1;

	while(b > 0)

	{

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

		a = a * a % MOD;

		b = b >> 1;

	}

	return res;

}

int main()

{

	scanf("%d",&n);

	int p,e;

	int ans1 = 1,ans3 = 0;

	int m = 1;

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

	{

		scanf("%d%d",&p,&e);

		m = m * power(p,e) % MOD;

		if(p <= 2)continue;

		int x = ans1,y = ans3;

		ans1 = (ans1 + (p - 1) * y) % MOD;

		ans3 = (ans3 + (p - 1) * x) % MOD; 

	}

	ans1 = (ans1 - 1 + MOD) % MOD;

	cout << ans1 << endl << ans3 << endl << (m - 1 - ans1 - ans3 + MOD + MOD) % MOD << endl;

	return 0;

}