BZOJ 1408 NOI2002 Robot 數論

題目大意：- -我不行了自己看

逗比題- - 用了這麼大篇幅來講述什麼是φ和μ- -

不過不是普通的φ和μ，有些變形- -

新定義的φ(1)=0，新定義的μ只計算奇質數，含有2為因子的數都按照μ值為零處理

我們首先求出第一問和第二問，即μ值不等於0的部分

由於μ的定義，μ值不等於0當且僅當每個質因數的次數都是1次

因此我們枚舉每個奇質數 計算加上這個奇質數之後φ值之和多出來的部分

由於φ是積性函數 所以前兩問可以在O(n)時間內出解

第三問可以用總答案減掉前兩問的答案

由於Σ[d|n]φ(d)=n，因此總答案就是m-1(此題1不算其它數的因數，去掉1)

用m-1減掉前兩問的答案就是第三問的答案

#include 
#include 
#include 
#include 
#define M 10100
#define MOD 10000
using namespace std;
struct abcd{
	int p,a;
	friend istream& operator >> (istream &_,abcd &x)
	{
		scanf("%d%d",&x.p,&x.a);
		return _;
	}
}prime_factors[1010];
int n,m,ans1,ans2,ans3;
int Quick_Power(int x,int y)
{
	int re=1;
	while(y)
	{
		if(y&1) (re*=x)%=MOD;
		(x*=x)%=MOD;y>>=1;
	}
	return re;
}
int main()
{
	int i;
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>prime_factors[i];
	for(i=1;i<=n;i++)
	{
		if(prime_factors[i].p==2)
			continue;
		int temp1=(ans1+ans2*(prime_factors[i].p-1)     )%MOD;
		int temp2=(ans2+(ans1+1)*(prime_factors[i].p-1) )%MOD;
		ans1=temp1;ans2=temp2;
	}
	m=1;
	for(i=1;i<=n;i++)
		(m*=Quick_Power(prime_factors[i].p,prime_factors[i].a) )%=MOD;
	(ans3=(m-1)-ans1-ans2+MOD*3)%=MOD;
	cout<