[Noi2002]Robot

BZOJ1408..
 
首先翻译下题意:
定义μ'(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;

}