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;
}