1014 Uniform Generator ACM

http://acm.hdu.edu.cn/showproblem.php?pid=1014

题目的英文实在是太多了 ，搞不懂。

最后才知道是用公式seed(x+1) = [seed(x) + STEP] % MOD 来计算随机数 ，问是否满足随机数。

初级版本：

思路：把所有的用该公式计算出来的数（存在数组中）都遍历出来，然后排序。由于数字是在0 到mod-1 之间，所以数组的下标必然等于数组的值，有一个不等于，就是bad chioce

#include <stdio.h>

#include <stdlib.h>

int cmp ( const void *p1 , const void *p2 )

{

    return *( int * )p1 - *( int * )p2 ;

}

int main ( )

{

    int step , mod ;

    while ( (scanf("%d %d",&step , &mod ) ) != EOF )

    {

        int i , seed[  ] = {  } ;

        seed[  ] =  ;

        for ( i =  ; i < mod ; i ++ )

            seed[ i ] = ( seed[ i- ] + step ) % mod ;

        qsort( seed , mod , sizeof ( int ) , cmp ) ;

        for ( i =  ; i < mod ; i ++ )

            if ( seed[ i ] != i )

                break ;

        if ( i != mod )

            printf("%10d%10d    Bad Choice\n\n", step , mod );

        if ( i == mod )

            printf("%10d%10d    Good Choice\n\n" , step , mod );

    }

    return ;

}

升级版本：

思路：只要有一个遍历出来的数和已经算出来的随机数相等 ，根据该公式，那么后来遍历出来的数，必然循环相等。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int visit[];

int main()

{

    int sept,mod;

    while(scanf("%d%d",&sept,&mod) != EOF)

    {

        int flag = ,n = ;

        memset(visit,,sizeof(visit));

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

        {

            n = (n + sept) % mod;

            if(visit[n])

            {

                flag = ;

                break;

            }

            else

            {

                visit[n] = ;

            }

        }

        if(flag)

        printf("%10d%10d    Bad Choice\n\n",sept,mod);

        else

        printf("%10d%10d    Good Choice\n\n",sept,mod);

    }

    return ;

}