BZOJ3288: Mato矩阵(欧拉函数 高斯消元)

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#define LL long long 
using namespace std;
const int MAXN = 1e7 + 10, mod = 1e9 + 7;
int N;
LL ans = 1;
int prime[MAXN], tot, vis[MAXN], phi[MAXN];
void GetPhi(int N) {
    phi[1] = 1;
    for(int i = 2; i <= N; i++) {
        if(!vis[i]) prime[++tot] = i, phi[i] = i - 1;
        for(int j = 1; j <= tot && i * prime[j] <= N; j++) {
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0) phi[i * prime[j]] = phi[i] * prime[j];
            else phi[i * prime[j]] = phi[i] * phi[prime[j]];
        }
    }
}
int main() {
    scanf("%d", &N);
    GetPhi(1e6 + 10);
    for(int i = 1; i <= N; i++) ans = (1ll * ans * phi[i]) % mod;
    printf("%lld", ans);
    return 0;
}
/*
123 321
*/