BZOJ_1408_[Noi2002]Robot

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。

$\sum\limits_{d|n}\phi(d)=n$

因此总和为n。

只需要求约数中$\mu$为1的$\varphi$和，$\mu$为-1的$\varphi$和。

这样，我们每个质因子只有一次贡献。

这次贡献会把之前的$\mu$从1变到-1，从-1变到1。

又因为phi是积性函数，每次都需要乘上$\varphi(p)=p-1$。

要注意2不是奇质数。一个数的约数不考虑1。

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <stdlib.h>

using namespace std;

#define mod 10000

int n,m,p,k,f[1050],g[1050];

int qp(int x,int y) {

    int re=1;

    while(y) {

        if(y&1) re=re*x%mod;

        x=x*x%mod;

        y>>=1;

    }

    return re;

}

int main() {

    scanf("%d",&n);

    m=1;

    int i;

    f[0]=1;

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

        scanf("%d%d",&p,&k); m=m*qp(p,k)%mod;

        if(p!=2) {

            f[i]=(f[i-1]+g[i-1]*(p-1)%mod)%mod;

            g[i]=(g[i-1]+f[i-1]*(p-1)%mod)%mod;

        }else {

            f[i]=f[i-1];

            g[i]=g[i-1];

        }

    }

    f[n]=(f[n]-1+mod)%mod;

    printf("%d\n%d\n%d\n",f[n],g[n],((m-f[n]-g[n]-1)%mod+mod)%mod);

}

巴特西

BZOJ_1408_[Noi2002]Robot_数学