首页 > 代码库 > BZOJ 3288: Mato矩阵
BZOJ 3288: Mato矩阵
Description
一个 \(n*n\) 行列式,\((i,j)=gcd(i,j)\)
Sol
线性筛.
这道题神奇的筛出来 \(phi\) ...
打表可以发现,一个数会被他所有的因子减掉因子的 \(phi\) ...
然后我就不会证明了...
Code
/************************************************************** Problem: 3288 User: BeiYu Language: C++ Result: Accepted Time:432 ms Memory:9100 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; typedef long long LL;const int N = 1e6+50;const LL p = 1e9+7; int n;LL ans;int pr[N],cp;int phi[N]; void Pre() { phi[1]=1,ans=1; for(int i=2;i<=n;i++) { if(!phi[i]) phi[i]=i-1,pr[++cp]=i; for(int j=1;j<=cp && (LL)pr[j]*i<=n;j++) { if(i%pr[j]) { phi[i*pr[j]]=phi[i]*(pr[j]-1); }else { phi[i*pr[j]]=phi[i]*pr[j]; } } }// for(int i=1;i<=n;i++) cout<<phi[i]<<" ";cout<<endl; for(int i=1;i<=n;i++) ans=(ans*phi[i])%p;} int main() { cin>>n; Pre(); cout<<ans<<endl; return 0;}
BZOJ 3288: Mato矩阵
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。