zoj 1314, 1278 - 行者无疆 始于足下 - 行走,思考,在路上

zoj 1314, 1278

xiaohanyu posted @ Tue, 25 May 2010 03:27:48 +0800 in Algorithm with tags ZJU Algorithm , 3197 readers

两道题目表面上看起来很相似,解法是不一样的。

1314的本质是给定数[tex]x, y[/tex],问[tex]ax (\bmod y), a = 1, 2, \cdots [/tex]的周期是多少。依稀记得同余理论和不定方程的某些结论,我猜测周期应该是[tex]\frac{y}{gcd(x, y)}[/tex],自己验证了下也是对的。具体证明涉及到同余和不定方程,高中的基础全忘了,叹。

程序ac一波三折,先是TLE,后来发现scanf()后面没有写!= EOF,可是这题也没说啥时算输入结束啊……看来是经验不足了;后来又是Presentation Error,仔细检查发现是四个空格输出成了五个空格……叹……

代码: 

#include <stdio.h>

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
    
int main(int argc, char *argv[])
{
    int step, mod;

    while (scanf("%d%d", &step, &mod) != EOF)
    {
        printf("%10d%10d", step, mod);
        if (gcd(step, mod) == 1)
        {
            printf ("    Good Choice\n");
        }
        else
        {
            printf ("    Bad Choice\n");
        }
        printf ("\n");
    }
    
    return 0;
}

zoj 1278和zoj1314很像,于是我尝试着用zoj1314的方法去解决,我甚至求出了通项公式:

[tex]y_n = (Z^{n-1}L + \frac{Z^{n-1} - 1}{Z - 1}I )\bmod M[/tex]

后来发现不行,因为这个式子的增量不是线性常数,需要另觅他法。很无耻的参考了这篇博客,难得体会到了代码之美,用数组做标记(我不知道是不是该这样说,或者hash table?)的手法,某些时候确实很管用,需要进一步熟悉。

代码贴一下吧……虽然是抄袭的^~~^:

#include <iostream>
#include <cstring>
using namespace std;

int main(int argc, char *argv[])
{
    int z, i, m, last, next;
    bool judge[10000];

    int count;
    int n = 1;

    while (cin >> z >> i >> m >> last)
    {
        if (z == 0 && i == 0 && m == 0 && last == 0)
        {
            break;
        }

        memset(judge, false, sizeof(judge));

        count = 0;
        while (true)
        {
            next = (z * last + i) % m;

            if (judge[next])
            {
                break;
            }

            last = next;
            judge[next] = true;

            count ++;
        }

        cout << "Case " << n++ << ": "  << count << endl;
    }
    
    return 0;
}

加油加油啊。


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee