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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

1295: [SCOI2009]最长距离

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

29640
来自专栏小樱的经验随笔

HDU 2080 夹角有多大II

夹角有多大II Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (J...

281100
来自专栏落影的专栏

iOS开发-OpenGL ES入门教程4

教程 OpenGL ES入门教程1-Tutorial01-GLKit OpenGL ES入门教程2-Tutorial02-shader入门 OpenGL E...

36150
来自专栏锦小年的博客

复杂网络(1)--图论的基本理论

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

287100
来自专栏Phoenix的Android之旅

一张图看懂开发和运营的思维差别

用Dijkstra算法很简单,我们需要 · 用 6*6矩阵 source[6][6]表示点之间的距离,也就是图中的权值 · 自己与自己的距离为0,无直接连接的距...

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
来自专栏温安适的blog

最小生产树Prim和Kruskal

489120
来自专栏算法修养

HOJ 2133&POJ 2964 Tourist(动态规划)

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

37080
来自专栏小鹏的专栏

tensorflow使用BN—Batch Normalization

注意:不要随便加BN,有些问题加了后会导致loss变大。 上一篇是 Batch Normalization的原理介绍,看一下tf的实现,加到卷积后面和全连接层...

1.1K70

扫码关注云+社区

领取腾讯云代金券