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

2018-07-19 05:35:40来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 386  Solved: 296
[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
n<=1000000

Output

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

Sample Input

5

Sample Output

16

HINT

 

Source

By taorunz

 

Orz PoPoQQQ

高斯消元之后发现对角线是欧拉函数。。

然后就做完了。

// 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
*/

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

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

下一篇:BZOJ4407: 于神之怒加强版(莫比乌斯反演 线性筛)