HDU 4951 Multiplication table(2014 Multi-University Training Contest 8)

思路如果进制为p 那么当x<p时（p-1）*（p-x）=(p-（x+1）) *p +x 因为x<p 所以没有进位所以高位上的数字为 p-（x+1）。

根据上面所述。只要我们能找出 p-1 那么我们根据(p-1)*(p-1)的高位为p-2 就能找出p-2 。找出p-2根据 (p-1)*(p-2)的高位为(p-3) 就能找出p-3.。。。。任务就转化成找出p-1。我们会发现从0-（p-2）都会出现在高位。唯有p-1不会出现。那么就知道要出高位没出现过的数字就为p-1 那么问题就解决了。由于题目有说读入数据量很大，可以加个读入优化。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<vector>

#include <iostream>

using namespace std;

int ans[];

bool bo[];

int a[][];

inline int ReadInt()//优化接受int数，省时间，具体内容自己看懂，当成模板使用

{

    char ch = getchar();

    int data = ;

    while (ch < '' || ch > '')

        ch = getchar();

    do

    {

        data = data *  + ch - '';

        ch = getchar();

    } while (ch >= '' && ch <= '');

    return data;

}

int s[][];

int main() {

    int p,ri=;

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

    {

        for(int i=;i<p;++i)bo[i]=false;

        for(int i=;i<p;++i)

        {

            for(int j=;j<*p;++j)

            {

                a[i][j]=ReadInt();

                if(!(j&))

                {

                    s[i][j>>]=a[i][j];

                    bo[a[i][j]]=true;

                }

            }

        }

        for(int i=;i<p;++i)

            if(!bo[i])

            {

                ans[p-]=i;

                break;

            }

        int pre=ans[p-];

        for(int i=p-;i>=;--i)

        {

            ans[i]=s[ans[p-]][pre];

            pre=ans[i];

        }

        printf("Case #%d:",++ri);

        for(int i=;i<p;++i)

            printf(" %d",ans[i]);

        puts("");

    }

    return ;

}

巴特西

HDU 4951 Multiplication table(2014 Multi-University Training Contest 8)

最新文章

热门文章