GCD Determinant 解题报告

http://www.cn210.com/onlinejudge/problemshow.php?pro_id=98

我们的OJ

Description

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: 

Input

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. 

Output

For each test case find and print the value Dn mod 1000000007.  

Sample Input

2
1 2
3
1 3 9
4
1 2 3 6

Sample Output

1
12
4

首先由于行列式交换行和列后值不变，我们可以把输入的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的欧拉函数

所以原体就被我们转换成了欧拉函数值的积,接下来就很好处理了

代码如下:

#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
using namespace std;

const long mod = 1000000007;
long x[1005];

long eular(long n)
{
    long res = 1, i;
    for(i = 2; i * i <= n; i ++)
    {
        if(n % i == 0)
        {
            n /= i;
            res *= (i - 1);
            while(n % i == 0)
                n /= i, res *= i;
        }
    }
    if(n > 1)
        res *= n - 1;
    return res;
}

int main()
{
    int n, i;
    long res;
    while(scanf("%d", &n) != EOF)
    {
        res = 1;
        for(i = 0; i < n; i ++)
            scanf("%ld", &x[i]);
        sort(x, x + n);
        for(i = 0; i < n; i ++)
            res = ((long long)res * (long long)eular(x[i])) % mod;
        printf("%ld\n", res);
    }
    return 0;
}