这是个数学题

证明似乎没法用照片的形式了好悲伤啊

题目大意:

给你一个神奇的集合S,对于任意S内元素的值都满足一个神奇的条件:对于任意的x(是S中的元素),那么x/i也是(当然x/i要是整数)

这样啊,我不信我用不了文字来表达...

题目链接:http://poj.org/problem?id=3910

这一个文章我得好好解释一下啥是行列式了....

行列式的求解很复杂...

对于一个行列式,我们知道这么几个性质:

1,第i行可以整体减掉第j行的值,行列式值不变(就像高斯消元那样)(可以乘以k倍)(列好像也行)

2,对于一个除了对角线外全空的行列式,值为对角线的积

3,交换两行,值不变(列也一样)

那么我们来考虑这样一个问题

原题的a1,a2...an改为1,2...n

那么我来做点"合情合理的推理"

|(1,1) (1,2) (1,3) (1,4)|

代码如下:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int modo=1000000007;
int phi(int x)
{
    int i;
    int t=x;
    for (i=2;i*i<=x;i++)
    {
        if (x%i==0)
        {
            t/=i;
            t*=(i-1);
            for (;x%i==0;)
            {
                x/=i;
            }
        }
    }
    if (x!=1)
    {
        t/=x;
        t*=(x-1);
    }
    return t;
}
int main()
{
    int n;
    for (;scanf("%d",&n)!=-1;)
    {
        int i;
        int p=1;
        for (i=0;i<n;i++)
        {
            int x;
            scanf("%d",&x);
            p=(long long)p*phi(x)%modo;
        }
        printf("%d\n",p);
    }
    return 0;
}

可是呢...我们还没证明完呢怎么能放过这题??!!

考虑上面的矩阵,我们定义一个叫做a,一个叫做b

那么,我们定义

b(1,i) + b(2,i) + ... + b(n,i) = a(n,i)

以此得到b矩阵

我们要证明两点:

b(i,j) = 0 (j != ki,k是整数)

b(i,j) = phi(i) (j = ki)

那么首先,第一行显然是对的...

对于第i行,如果j!=ki的话

那么存在gcd(i,j)这么一行

满足b(1,j) + b(2,j) + ... + b((i,j),j) = (i,j)

那么剩下来的都不是j的因数,所以值都是0

所以b((i,j)+1,j) + ... + b(i,j) = 0所以值是0

那么b(i,j) = phi(i)也很好证明,因为sigma(d是i的约数,phi(i)) = i,所以直接反过来推即可

证明完毕

然而问题又来了..

题目给的是a1,a2...an而不是1,2...n

其实这个解决方案也很简单了啊...和上面证明是差不多的只要排个序就好了...(似乎给的性质还是很有用的)

大概真正和t有关的行全是t的约数的行,我们把所有别的行(和列)"抽掉"即可

例如