[Noi2002]Robot
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
首先翻译下题意：
定义μ'(n) =
{
μ(n) (n = 1(mod 2))
0 (n = 0(mod 2))
}
第一问问n的约数中μ'(n)为1的的欧拉函数之和
第二问问n的约数中μ'(n)为-1的的欧拉函数之和
第三问问n的约数中μ'(n)为0的的欧拉函数之和
先看一、二问:
可知对于某个d|n,若μ'(d) ≠ 0,则d没有平方因子，因此d = Π(i=1,k且pi≠2)pi*x,其中x为零或一,
而phi(d) = Π(i=1,k)(pi-1)*x,并且，Σ(d|n且d=1(mod 2))phi(d)即为第一问答案，
而Σ(d|n且d=0(mod 2))phi(d)即为第二问答案。
为了方便，我们构造向量q,其中qi = pi - 1表示q的第i个元素,那么从q中任取几个元素相乘，若有奇数个则累加
r1,偶数个则累加r2，最后r2即为第一问答案，r1即为第二问答案。
接下来我们可以有一个递推(我也不知道算不算DP，因为比较奇怪...）
对于r1，我们令f1(x)为只取q的前x个元素的r1，f2(x)为只取q的前x个元素的r2,因此我们有:
f1(i) = f1(i-1) + R(qi)
这里R(qi)表示包含了qi的新取法，它相当于在原来为偶数的取法中加一个qi,得到新的答案，因为Σ(A*qi) =qi*Σ(A),
而这里Σ(A)就是取偶数个的答案，也就是f2(i-1),另外qi单独的也是一个答案,因此我们得到f1(i)的表达式:
f1(i) = f1(i-1) + qi*f2(i-1) + qi
类似的我们可以得到f2(i)的表达式:
f2(i) = f2(i-1) + qi*f1(i-1)
这样就得到了r1 = f1(k),r2 = f2(k),接下来让我们来计算第三问答案r3
因为r1+r2+r3为所有M的约数(除了1）的欧拉函数之和，
而M的所有约数的欧拉函数之和就等于M，因此r1+r2+r3就等于M-1(因为没有算1)，因此r3=M-r1-r2，即可算得r3
代码如下:
#include <stdio.h>
const int N = 2000;
int p2[N + 100];
int p[N + 100];
int e[N + 100];
int r1[N + 100];
int r2[N + 100];
int r3 = 0;
int n = 0;
const int M = 10000;
int pow(int a,int b,int c)
{
int r = 1;
int m = (1 << 30);
while(m)
{
r = ((r * r) % c);
if(m & b)
r = ((r * a) % c);
m >>= 1;
}
return r;
}
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i++)
{
scanf("%d%d",p + i,e + i);
p2[i] = p[i] - 1;
}
for(int i = 1;i <= n;i++)
{
if(p[i] == 2)
continue;
r1[i] = (int)((1LL * p2[i] + 1LL * r1[i - 1] + 1LL * r2[i - 1] * p2[i]) % (1LL * M));
r2[i] = (int)((1LL * r2[i - 1] + 1LL * r1[i - 1] * p2[i]) % (1LL * M));
}
r3 = 1;
for(int i = 1;i <= n;i++)
{
r3 = (int)((1LL * r3 * pow(p[i],e[i],M)) % (1LL * M));
}
r3 = (r3 - r1[n] - r2[n] - 1);
while(r3 < 0)
r3 += M;
printf("%d\n%d\n%d\n",r2[n],r1[n],r3);
return 0;
}
评论 (0)
