BZOJ3288: Mato矩阵(欧拉函数 高斯消元)
2024-09-08 01:00:22
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
Orz PoPoQQQ
高斯消元之后发现对角线是欧拉函数。。
然后就做完了。
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int MAXN = 1e7 + , mod = 1e9 + ;
int N;
LL ans = ;
int prime[MAXN], tot, vis[MAXN], phi[MAXN];
void GetPhi(int N) {
phi[] = ;
for(int i = ; i <= N; i++) {
if(!vis[i]) prime[++tot] = i, phi[i] = i - ;
for(int j = ; j <= tot && i * prime[j] <= N; j++) {
vis[i * prime[j]] = ;
if(i % prime[j] == ) 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 + );
for(int i = ; i <= N; i++) ans = (1ll * ans * phi[i]) % mod;
printf("%lld", ans);
return ;
}
/*
123 321
*/
最新文章
- deiban8 sourcelist
- ubuntu和windows上pip和windows上conda国内源更新module
- .NET文档生成工具ADB使用图文教程
- 关于Currency类型和 TCurrencyFiled的悲剧
- 设置EDIUS字幕时有哪些要注意的
- 深度观察:腾讯收购大众点评背景下的O2O大格局
- BZOJ_3670_[NOI2014]_动物园_(kmp)
- HTML-滚动字幕的源代码(可作滚动公告)
- C++ 檔案、資料夾、路徑處理函式庫:boost::filesystem
- VB6.0数据库开发五个实例——罗列的总结
- 用XAML做网页!!—广告展示区
- swust oj(0088)表达式的转换
- treeview调用数据库成树
- java Calendar的学习分享
- Oarcle之序列
- Running tests on PyCharm using Robot Framework
- oracle基础——内存管理、优化
- PCA(主成分分析)和LDA详解
- 关于php的array_diff和array_diff_assoc的使用总结
- Zabbix邮件告警提示Couldn&#39;t resolve host name解决办法