题目大意:给定a1,a2,...,an,求
由于φ是积性函数,我们可以将i1i2...in分解质因数,对于每个质因数分开讨论,求积即可
将每个a分解质因数,假设分解后某个质数p在每个ai中的次数分别是bi,那么p对答案的贡献就是
于是对p^j维护一个前缀和,直接计算即可
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MOD 1000000007
using namespace std;
struct abcd{
int p,a;
bool operator < (const abcd &x) const
{
if(p!=x.p)
......
阅读全文