# GCD Determinant 解题报告

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

## 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

dp[i] = x[i] - sum{x[i]的因子对应的dp值(即:gcd(xj,xi) == xj)? dp[j]: 0;}

y可以化简为y = xp * yp,其中xp 为小于y的最大的x的因子,且yp是x的某个因子的最大公约数为1的数字中最大的数字.

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

0 条评论

## 相关文章

### 1295: [SCOI2009]最长距离

1295: [SCOI2009]最长距离 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 960  Solve...

29640

281100

36150

### 复杂网络（1）--图论的基本理论

1 图论的基本概念 1.1 图（graph）及其分类 （1） 图的定义：图是由点集V={vi}以及V中元素无序对的集合E={ek}所构成的二元组，记为G=(...

287100

8710

463100

### Leetcode 200 Number of Islands 并查集

Given a 2d grid map of '1's (land) and '0's (water), count the number of islan...

26170

489120

### HOJ 2133&POJ 2964 Tourist（动态规划）

Tourist Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 1503...

37080

1.1K70