BZOJ 3288: Mato矩阵

3288: Mato矩阵

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 295  Solved: 224
[Submit][Status][Discuss]

Description

Mato同学最近正在研究一种矩阵，这种矩阵有n行n列第i行第j列的数为gcd(i,j)。
例如n=5时，矩阵如下：

1 1 1 1 1
1 2 1 2 1
1 1 3 1 1
1 2 1 4 1
1 1 1 1 5

Mato想知道这个矩阵的行列式的值，你能求出来吗?

Input

一个正整数n mod1000000007

Output

n行n列的Mato矩阵的行列式。

Sample Input

5

Sample Output

16

HINT

对于100%的数据，n<=1000000。

Source

By taorunz

[Submit][Status][Discuss]

打表发现矩阵高斯消元之后，对角线上是欧拉函数，即n阶的Mato矩阵的行列式就是$prod_{i=1}^{n}{phi(i)}$。

#include <cstdio>

const int mxn = 1000005;
const int mod = 1000000007;

int n;

int cnt;
int pri[mxn];
int phi[mxn];
int que[mxn];

signed main(void) {
  scanf("%d", &n);

  phi[1] = 1;

  for (int i = 2; i <= n; ++i) {
    if (pri[i] == 0)que[cnt++] = i, phi[i] = i - 1;
    for (int j = 0; j < cnt && que[j] * i <= n; ++j) {
      pri[que[j] * i] = que[j];
      if (i % que[j] == 0) {
	phi[que[j] * i] = phi[i] * que[j];
	break;
      }
      else phi[que[j] * i] = phi[i] * (que[j] - 1);
    }
  }

  int ans = 1;

  for (int i = 1; i <= n; ++i)
    ans = (1LL * ans * phi[i]) % mod;

  printf("%d
", ans);
}

　　

@Author: YouSiki