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[ 100001 ] = { 0 } ; seed[ 0 ] = 0 ; for ( i = 1 ; i < mod ; i ++ ) seed[ i ] = ( seed[ i-1 ] + step ) % mod ; qsort( seed , mod , sizeof ( int ) , cmp ) ; for ( i = 0 ; i < mod ; i ++ ) if ( seed[ i ] != i ) break ; if ( i != mod ) printf("%10d%10d Bad Choice ", step , mod ); if ( i == mod ) printf("%10d%10d Good Choice " , step , mod ); } return 0; }
升级版本:
思路:只要有一个遍历出来的数和已经算出来的随机数相等 ,根据该公式,那么后来遍历出来的数,必然循环相等。
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> using namespace std; int visit[100005]; int main() { int sept,mod; while(scanf("%d%d",&sept,&mod) != EOF) { int flag = 0,n = 0; memset(visit,0,sizeof(visit)); for(int i = 1; i <= mod; i++) { n = (n + sept) % mod; if(visit[n]) { flag = 1; break; } else { visit[n] = 1; } } if(flag) printf("%10d%10d Bad Choice ",sept,mod); else printf("%10d%10d Good Choice ",sept,mod); } return 0; }