absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
100506 I 解题报告
100753 A 解题报告

POJ 3910 解题报告

absi2011 posted @ Nov 22, 2015 09:09:11 PM in 刷题记录 with tags POJ 行列式 数学题 , 596 阅读

这是个数学题

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

题目大意:

给你一个神奇的集合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)|

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

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

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

PS:(a,b)是gcd(a,b)简写
对于这样的行列式,我们求值,计算,得
|1 1 1 1|
|1 2 1 2|
|1 1 3 1|
|1 2 1 4|
那么转化为
|1 1 1 1|
|0 1 0 1| (减第一行)
|0 0 2 0| (减第一行)
|0 0 0 2| (减第二行)
也许更大一点更好发现规律?
|1 1 1 1 1 1|
|1 2 1 2 1 2|
|1 1 3 1 1 3|
|1 2 1 4 1 2|
|1 1 1 1 5 1|
|1 2 3 2 1 6|
变成
|1 1 1 1 1 1|
|0 1 0 1 0 1|
|0 0 2 0 0 2|
|0 0 0 2 0 0|
|0 0 0 0 4 0|
|0 0 0 0 0 2|
那么我们发现,第i行i列是phi(i)
那么就好办了,我们可以写代码了~好开心啊又AC了一题

代码如下:

#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的约数的行,我们把所有别的行(和列)"抽掉"即可

例如

|1 1 1 1 1 1|
|1 2 1 2 1 2|
|1 1 3 1 1 3|
|1 2 1 4 1 2|
|1 1 1 1 5 1|
|1 2 3 2 1 6|
变成
|1 1 1 1 1 1|
|0 1 0 1 0 1|
|0 0 2 0 0 2|
|0 0 0 2 0 0|
|0 0 0 0 4 0|
|0 0 0 0 0 2|
==>(保留1,2,3,6行/列)
|1 1 1 1|
|1 2 1 2|
|1 1 3 3|
|1 2 3 6|
变成
|1 1 1 1|
|0 1 0 1|
|0 0 2 2|
|0 0 0 2|
可以发现这是不影响的..

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter