GCD Determinant 解题报告
Last updated
Was this helpful?
Last updated
Was this helpful?
我们的OJ
We say that a set S = {x1, x2, ..., xn} is factor closed if for any xi ∈ S and any divisor d of xi we have d ∈ S. Let's build a GCD matrix (S) = (sij), wheresij = GCD(xi, xj) - the greatest common divisor of xi and xj. Given the factor closed set S, find the value of the determinant:
The input contains several test cases. Each test case starts with an integer n (0 < n < 1000), that stands for the cardinality of S. The next line contains the numbers of S: x1, x2, ..., xn. It is known that each xi is an integer, 0 ≤ xi ≤ 2*109. The input data set is correct and ends with an end of file.
For each test case find and print the value Dn mod 1000000007.
首先由于行列式交换行和列后值不变,我们可以把输入的X进行排序,然后列出的矩阵行列式值等于原行列式
然后,由于题目告诉我们输入的元素是封闭的(即如果a在S中,a的所有因子都在S中)
我们对行列式进行三角阵的化简可以得出对于对角线上的元素xi=gcd(xi,xi)化简结果dp[i]有
dp[i] = x[i] - sum{x[i]的因子对应的dp值(即:gcd(xj,xi) == xj)? dp[j]: 0;}
这里我们可以看出它和欧拉函数很像,现在证明它就是欧拉函数
欧拉函数表示的是小于等于本身且最大公约数=1的数字的个数.
显然对于x,诺y<=x且gcd(x,y) > 1
y可以化简为y = xp * yp,其中xp 为小于y的最大的x的因子,且yp是x的某个因子的最大公约数为1的数字中最大的数字.
对于每个因子的每个yp必然存在一个xp使y的值不同
也就是说每个y都对应了一个因子的一个yp
所以x的欧拉函数等于x -(y的个数)就等于x - 每个因子的欧拉函数
所以我们要求的dp[i]就是xi的欧拉函数
所以原体就被我们转换成了欧拉函数值的积,接下来就很好处理了
代码如下: