题目描述
输入
输出
样例输入
3
2 1
3 2
5 1
样例输出
8
6
75
题解
语文题+数论+dp
花了大段讲述什么叫mu，什么叫phi，只是新定义的mu将2看作有平方因子，新定义的phi(1)=0。
要求的就是mu值为1的数的phi值之和、所有mu值为-1的phi值之和、以及所有mu值为0的phi值之和。
先只考虑前两种，此时无论质因子有多少个，能够使用的只有1个。如果p不是2，那么就有两种情况：使用和不使用。使用的话，素数个数+1，也就是mu变为相反数。
又因为phi是积性函数，所以之前的phi的和乘上p-1就是新得到的phi值和。
用一个类似于dp的思想求出这两个答案，最后由于∑phi(d)(d|m)=m，那么三种答案之和应该为m-1（因为题目中说1不算做约数），所以m-1减去前两种即可得到第三种。
处理ans1和ans2的时候应该先把phi1当作1处理，然后再减掉。
#include <cstdio>
#include <algorithm>
#define mod 10000
using namespace std;
int pow(int x , int y)
{
int ans = 1;
while(y)
{
if(y & 1) ans = ans * x % mod;
x = x * x % mod , y >>= 1;
}
return ans;
}
int main()
{
int k , m = 1 , i , p , e , ans1 = 1 , ans2 = 0 , t;
scanf("%d" , &k);
while(k -- )
{
scanf("%d%d" , &p , &e) , m = m * pow(p , e) % mod;
if(p != 2) t = ans1 , ans1 = (ans1 + ans2 * (p - 1)) % mod , ans2 = (ans2 + t * (p - 1)) % mod;
}
ans1 = (ans1 - 1 + mod) % mod;
printf("%d\n%d\n%d\n" , ans1 , ans2 , (m - ans1 - ans2 - 1 + 2 * mod) % mod);
return 0;
}