Description
(nle 10^6). 一个 (n*n) 的矩阵, (A_{i, j}=gcd(i, j)) . 求 (det Apmod {10^9+7})
Analysis
不会做啊 , 打个表? 找不到规律啊, 大佬们怎么看出来是 (varphi) 的啊
以为自己行列式求错了, 去调了一下发现奥妙规律.
当消元进行到第 (i) 行, 第 (i) 行还没开始动手消别人时, 有:
(forall i~|~d, A_{i,d}=A_{d,i}=A_{i,i}) (1)
(forall i ot|~d, A_{i,d}=A_{d,i} = 0) (2)
此时 倍加行变换不用乘系数, 直接是 (A_{id,*}-=A_{i,*}) (3)
于是写了个调和级数求解对角线.... 今天第四道题比正解多一个 (log) QAQ
正解是 : 消完后 (A_{i,i} = varphi(i)). (4)
(对应表中的规律为: 质数->质数-1, 相邻项比值全是偶数)
Prove
归纳证明一下, 消元进行到第 (1) 行时, 结论 ((1)(2)(3)(4)) 同时成立.
考虑归纳, 假设之前消元进行良好, 当消元进行到第 (i) 行时
对于第 (i) 列的数 (A_{j, i}) , 由于 (i) 之前的行都是按照 ((3)) 的方式进行消元
又根据 ((1)(2)) 能贡献到 (A_{j,i}) 的行号 (d) , 必定满足 (d|i, j) 即 (d|(i,j))
有 (sum_{d|n} varphi(d)=n) 以及 (sum_{d|n, d<n}varphi(d)=varphi (n)) 两种情况
当 (i|j) 时为后者 , 剩下个 (varphi (i)) ((i) 的因数 (i) 还没动手)
当 (i ot|j) 时为前者, 剩下个 (0) ((gcd(i,j) < i, 即gcd的因数已全部贡献))
对于第 (i) 行的数 (A_{i,j}) 也可同理证明.
此时 消元进行到 (i) 行前时矩阵的模式确实满足 ((1)(2)(3)(4)), 证毕.