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