[SPOJ 2832] | Eurce's Blog

数论

题意：输入一个最多200*200的行列式a和一个正整数p，求|a|%p。

分析：集训队论文集里《欧几里得算法的应用》的第一道例题。非常巧妙，用GCD思想作模系统下的高斯消元。实现的时候大致要注意以下几点：
（1）尽量减少辗转相除的次数；
（2）尽量少用模运算；
（3）消元过程中算出答案为0提前结束；
（4）尽量避免整行swap；
（5）手动解释输入；
（6）尽量不用long long。

TLE了一整晚后，成功刷入第一版。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long

int n,p,d[200][200];
ll ans;

int gi()
{
    char c;
    while((c=getchar())!='-'&&(c<'0'||c>'9'));
    int d,e=1;
    if(c=='-')
    {
        e=-1;
        c=getchar();
    }
    d=c-'0';
    while((c=getchar())>='0'&&c<='9')
        d=d*10+c-'0';
    return d*e;
}

void init()
{
    ll i,j;
    ans=1;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            d[i][j]=gi();
            if(abs(d[i][j])>=p)
                d[i][j]%=p;
            if(d[i][j]<0)
                d[i][j]+=p;
        }
    }
}

void calc(int h,int i,int j)
{
    int k;
    ll a,e;
    if(d[i][h]<d[j][h])
        swap(i,j);
    while(d[j][h])
    {
        a=d[i][h]/d[j][h];
        for(k=h;k<n;k++)
        {
            e=d[i][k]-a*d[j][k];
            if(abs(e)>=p)
                e%=p;
            if(e<0)
                e+=p;
            d[i][k]=e;
        }
        if(d[i][h]<d[j][h])
            swap(i,j);
    }
}

void solve()
{
    int i,j,k,l;
    for(i=0;i<n;i++)
    {
        for(j=i;j<n&&!d[j][i];j++);
        if(j==n)
        {
            puts("0");
            return;
        }
        if(j>i)
        {
            for(l=i;l<n;l++)
                swap(d[i][l],d[j][l]);
            ans=-ans;
        }
        for(l=i,j=l+1;j<n;j++)
        {
            calc(i,j,l);
            if(!d[l][i])
                l=j;
        }
        if(l>i)
        {
            ans=-ans;
            for(k=i;k<n;k++)
                swap(d[i][k],d[l][k]);
        }
    }
    for(i=0;i<n;i++)
        ans=ans*d[i][i]%p;
    printf("%lldn",(ans%p+p)%p);
}

int main()
{
    while(~scanf("%d%d",&n,&p))
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

int n,p,d[200][200];

ll ans;

int gi()

{

char c;

while((c=getchar())!='-'&&(c<'0'||c>'9'));

int d,e=1;

if(c=='-')

{

e=-1;

c=getchar();

}

d=c-'0';

while((c=getchar())>='0'&&c<='9')

d=d*10+c-'0';

return d*e;

}

void init()

{

ll i,j;

ans=1;

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{

d[i][j]=gi();

if(abs(d[i][j])>=p)

d[i][j]%=p;

if(d[i][j]<0)

d[i][j]+=p;

}

void calc(int h,int i,int j)

{

int k;

ll a,e;

if(d[i][h]<d[j][h])

swap(i,j);

while(d[j][h])

{

a=d[i][h]/d[j][h];

for(k=h;k<n;k++)

{

e=d[i][k]-a*d[j][k];

if(abs(e)>=p)

e%=p;

if(e<0)

e+=p;

d[i][k]=e;

}

if(d[i][h]<d[j][h])

swap(i,j);

}

void solve()

{

int i,j,k,l;

for(i=0;i<n;i++)

{

for(j=i;j<n&&!d[j][i];j++);

if(j==n)

{

puts("0");

return;

}

if(j>i)

{

for(l=i;l<n;l++)

swap(d[i][l],d[j][l]);

ans=-ans;

}

for(l=i,j=l+1;j<n;j++)

{

calc(i,j,l);

if(!d[l][i])

l=j;

}

if(l>i)

{

ans=-ans;

for(k=i;k<n;k++)

swap(d[i][k],d[l][k]);

}

for(i=0;i<n;i++)

ans=ans*d[i][i]%p;

printf("%lldn",(ans%p+p)%p);

}

int main()

{

while(~scanf("%d%d",&n,&p))

{

init();

solve();

}

return 0;

}