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 ; }