「2019夏令营提高组」数论线代全家桶

题目链接

题意

已知 $n\times n$ 矩阵 $A$ 满足 $A_{i,j}=ij\cdot\gcd(i,j)$，求 $\det(A)$。

多组询问。

思路

显然可以改为求 $X_{i,j}=\gcd(i,j)$ 的 $\det(X)$，最后再将答案乘上 $\prod_{i=1}^ni^2$ 即可。

暴力高斯消元可以得到下面的上三角矩阵：

$\det(X)=\det\left( \begin{bmatrix} 1&1&1&1&1&1&\cdots\\ 0&1&0&1&0&1&\cdots\\ 0&0&2&0&0&2&\cdots\\ 0&0&0&2&0&0&\cdots\\ 0&0&0&0&4&0&\cdots\\ 0&0&0&0&0&2&\cdots\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots \end{bmatrix} \right)$

可以发现主对角线上排列着欧拉函数，所以可以线筛出欧拉函数得到 AC。

但是如何证明？

EI 给出了线性代数的方法。

设 $X\times U=V$，则对于向量 $V_i$：

$\begin{aligned} V_i&=\sum_jU_j\cdot\gcd(i,j)\\ &=\sum_jU_j\sum_{d|\gcd(i,j)}\varphi(d)\\ &=\sum_{d|i}\left(\varphi(d)\cdot\sum_{d|j}U_j\right) \end{aligned}$

令 $f(i)=\varphi(i)\cdot\sum_{i|j}U_j$，$g(i)=\sum_{i|j}U_j$，则：

$\begin{aligned} V_i&=\sum_{d|i}f(d)\\ f(i)&=\varphi(i)\cdot g(i)\\ g(i)&=\sum_{i|j}U_j \end{aligned}$

对矩阵分步进行乘法，即把 $X$ 看成三个矩阵的乘积。

根据行列式的性质，$U\to g$、$f\to V$ 时行列式并没有变化（因为都是向量之间的加减）。
$g\to f$ 时，第 $i$ 个向量乘了 $\varphi(i)$，所以行列式增大到原来的 $\prod_i\varphi(i)$ 倍了。

实现

预处理答案即可。

代码

#include<cstdio>
#include<vector>
using namespace std;
const int N=1e7;
int t,p,n;
int phi[N+1];
int res[N+1];
void initPhi()
{
    static bool npri[N+1];
    static vector<int> pri;
    phi[1]=1;
    for(int i=2;i<=N;++i) {
        if(!npri[i]) {
            pri.push_back(i),phi[i]=i-1;
        }
        for(int j:pri) {
            int prod=i*j;
            if(prod>N) {
                break;
            }
            npri[prod]=true;
            if(i%j==0) {
                phi[prod]=phi[i]*j;
                break;
            } else {
                phi[prod]=phi[i]*phi[j];
            }
        }
    }
    return;
}
int main()
{
    freopen("all.in","r",stdin);
    freopen("all.out","w",stdout);
    scanf("%d%d",&t,&p);
    initPhi();
    res[0]=1;
    for(int i=1;i<=N;++i) {
        res[i]=1ll*res[i-1]*phi[i]%p*i%p*i%p;
    }
    while(t--) {
        scanf("%d",&n);
        printf("%d\n",res[n]);
    }
    return 0;
}

致谢

感谢 EI 给出了精妙证明。
感谢 PinkRabbit 对式子的解释。