題目鏈接：

3288: Mato矩陣

Time Limit:?10 Sec??Memory Limit:?128 MB

Description

Mato同學(xué)最近正在研究一種矩陣，這種矩陣有n行n列第i行第j列的數(shù)為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

一個正整數(shù)n?mod1000000007

Output

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

Sample Input

5

Sample Output

16 題意： 思路： 進行行列變換后得到對角行列式,結(jié)果就是對角行列式的對角線上的積,變換后是歐拉函數(shù)值; AC代碼： /**************************************************************Problem: 3288User: LittlePointerLanguage: C++Result: AcceptedTime:572 msMemory:5196 kb ****************************************************************/#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <bits/stdc++.h> #include <stack> #include <map>using namespace std;#define For(i,j,n) for(int i=j;i<=n;i++) #define mst(ss,b) memset(ss,b,sizeof(ss));typedef long long LL;template<class T> void read(T&num) {char CH; bool F=false;for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar());for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());F && (num=-num); } int stk[70], tp; template<class T> inline void print(T p) {if(!p) { puts("0"); return; }while(p) stk[++ tp] = p%10, p/=10;while(tp) putchar(stk[tp--] + '0');putchar('\n'); }const LL mod=1e9+7; const double PI=acos(-1.0); const int inf=1e9; const int N=1e5+20; const int maxn=1e6+4; const double eps=1e-12;int phi[maxn];inline LL solve(int le) {LL sum=1;for(int i=2;i<=le;i++){if(!phi[i]){for(int j=i;j<=le;j+=i){if(!phi[j])phi[j]=j;phi[j]=phi[j]/i*(i-1);}}sum=sum*phi[i]%mod;}return sum; }int main() {int n;read(n);cout<<solve(n)<<"\n";return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/zhangchengc919/p/5818807.html

總結(jié)

以上是生活随笔為你收集整理的bzoj-3288 3288: Mato矩阵(数论)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。