Nescafe XXXVII 万物皆数

2015.01.04 19:07 Sun| 2 visits oi_2015| 2015_刷题日常| Text

Problem

Description

最早把数的概念提到突出地位的是毕达哥拉斯学派。他们很重视数学,企图用数来解释一切。宣称数是宇宙万物的本原,研究数学的目的并不在于使用而是为了探索自然的奥秘。

他同时任意地把非物质的、抽象的数夸大为宇宙的本原,认为“万物皆数”,“数是万物的本质”,是“存在由之构成的原则”,而整个宇宙是数及其关系的和谐的体系。毕达哥拉斯将数神秘化,说数是众神之母,是普遍的始原,是自然界中对立性和否定性的原则。 毕达哥拉斯学派的学者曾经研究过一种由数字构成的 N×N 的方阵,其中第 i 行第 j 列的数字是 i 和 j 的最大公约数,早在公元前学者 们就发现这个方阵具有许多非常神奇的性质, 时至今日,公因数方阵仍然在不断焕发新的光彩。 现代数学家用线性代数的方法研究它时, 发现这种方阵可以表示为公因数矩阵,其行列式也有着十分巧妙的规律,借助快速计算模型的普及,求解 N 阶公约数矩阵行列式的值成为了一个富有挑战性的问题。

Input

仅有一个正整数 N,N 的含义如题中所描述。

Output

仅包含一个整数,表示 N 阶公约数矩阵行列式的值除以 $10^9+7$ 的余数。

Sample Input

4

Sample Output

4

Hint

对于 20%的数据,N≤10。

对于 50%的数据,N≤200。

对于 100%的数据,N≤10^7。

Solution

大神从石家庄风尘仆仆地来长春,为我们带来了好多考试题以及什么是行列式。

行列式有好多好多性质,其中一条是可以高斯消元,之后得到的矩阵对角线的乘积即为行列式的值。于是,我平生第二次写高斯消元。

各种回忆+乱搞。。。。。。

之后把矩阵对角线输出,观察一下,惊喜地发现:好像是欧拉函数的积……然后快乐地写线性筛。

至于证明,可以用到莫比乌斯函数的一条性质……显然我根本推不出来,好在有一颗明亮的大眼睛 2333。

其实这也是很显然的事情:

观察数据范围要求 $\mathcal O(n)$ ,能够线性筛的东西显然不是逆元,不是素数,不是莫比乌斯函数,那么当然只剩下欧拉函数了……

Code

正解就是简单的欧拉函数的乘积……

下面的代码是行列式求值的模板,稍加修改后是本题50%正解……

long long det(int n, long long d[N][N])
{
    int cnt = 0;
    for(int i=0; i<n; i++)
    {
        if(d[i][i] == 0)
        {
            for(int j=i+1; j<n; j++)
                if(d[j][i]){
                    for(int k=0; k<n; k++)
                        swap(d[i][k], d[j][k]);
                    break;
                }
            if(d[i][i] == 0) return 0;
            cnt++;
        }
        for(int j=i+1; j<n; j++)
        {
            long long t = d[j][i]/d[i][i];
            for(int k=n-1; k>=0; k--)
                d[j][k] = d[j][k]-d[i][k]*t, d[j][k] %= mod;
        }
    }
    long long re = cnt&1 ? -1 : 1;
    for(int i=0; i<n; i++) re *= d[i][i], re %= mod;
    return re;
}