BZOJ3560: DZY Loves Math V(欧拉函数)

#include<cstdio>
#include<algorithm>
#define LL long long 
#define int long long 
using namespace std;
const int MAXN = 1e6 + 10, mod = 1e9 + 7;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int T, N, M;
struct Node {
    int p, a;
    bool operator < (const Node &rhs) const {
        return p == rhs.p ? a < rhs.a : p < rhs.p;
    }
}s[MAXN];
int tot = 0;
void insert(int x) {
    for(int i = 2; i * i <= x; i++) {
        if(!(x % i)) {
            s[++tot].p = i;
            while(!(x % i)) 
                x /= i, s[tot].a++;
        }
    }
    if(x > 1) s[++tot] = (Node) {x, 1};
}
int fastpow(int a, int p, int mod) {
    int base = 1;
    while(p) {
        if(p & 1) base = (base * a) % mod;
        a = (a * a) % mod; p >>= 1;
    }
    return base % mod;
}
int calc(int l, int r) {
    static int sum[31] = {}; sum[0] = 1;
    for(int i = 1; i <= s[r].a; i++) sum[i] = sum[i - 1] * s[l].p % mod;
    for(int i = 1; i <= s[r].a; i++) sum[i] = (sum[i - 1] + sum[i]) % mod;
    int rt = 1;
    for(int i = l; i <= r; i++) rt = (rt * sum[s[i].a]) % mod;
    rt--; 
    rt = (rt * fastpow(s[l].p, mod - 2, mod) + mod) % mod;
    rt = (rt * (s[l].p - 1) + mod) % mod;
    return (rt + 1) % mod;
}
main() {
//    freopen("a.in", "r", stdin);
    N = read();
    for(int i = 1; i <= N; i++) 
        insert(read());
    sort(s + 1, s + tot + 1);
    int pre = 0, ans = 1;
    for(int i = 1; i <= tot; i++) 
        if(s[i].p != s[i + 1].p || i == tot)
            ans = (ans * calc(pre + 1, i)) % mod, pre = i;
    printf("%lld", (ans + mod) % mod);
}
/*
3
600
1010
15010

*/