UVAOJ 350 基础题 伪随机数 数论
发布日期:2022-03-30 20:19:26 浏览次数:12 分类:博客文章

本文共 2916 字,大约阅读时间需要 9 分钟。

 Pseudo-Random Numbers 

Computers normally cannot generate really random numbers, but frequently are used to generate sequences of pseudo-random numbers. These are generated by some algorithm, but appear for all practical purposes to be really random. Random numbers are used in many applications, including simulation.


A common pseudo-random number generation technique is called the linear congruential method. If the last pseudo-random number generated was L, then the next number is generated by evaluating (  , where Z is a constant multiplier, I is a constant increment, and M is a constant modulus. For example, suppose Z is 7, I is 5, and M is 12. If the first random number (usually called the seed) is 4, then we can determine the next few pseudo-random numbers are follows:



As you can see, the sequence of pseudo-random numbers generated by this technique repeats after six numbers. It should be clear that the longest sequence that can be generated using this technique is limited by the modulus, M.


In this problem you will be given sets of values for ZIM, and the seed, L. Each of these will have no more than four digits. For each such set of values you are to determine the length of the cycle of pseudo-random numbers that will be generated. But be careful: the cycle might not begin with the seed!



Each input line will contain four integer values, in order, for ZIM, and L. The last line will contain four zeroes, and marks the end of the input data. L will be less than M.



For each input line, display the case number (they are sequentially numbered, starting with 1) and the length of the sequence of pseudo-random numbers before the sequence is repeated.


Sample Input


7 5 12 45173 3849 3279 15119111 5309 6000 12341079 2136 9999 12370 0 0 0


Sample Output


Case 1: 6Case 2: 546Case 3: 500Case 4: 220
1 #include
      2 #include
       3 #include
        4 #include
         5 #include
          6 #include
           7 #include
            8 #include
             9 #include
             10 #include
              11 #include
              12 #include
                13 #include
                 14 #include
                  15 #include
                   16 #include
                    17 #include
                     18 #include
                      19 #define eps 1e-620 #define INF 0x3f3f3f3f21 #define PI acos(-1.0)22 #define ll __int6423 #define LL long long24 #define lson l,m,(rt<<1)25 #define rson m+1,r,(rt<<1)|126 //#define M 100000000727 using namespace std;28 //以上内容直接无视~29 30 int is_used[11000];31 int main()32 {int T=0,Z,I,M,L,ans,l;33
//freopen("out.txt","w",stdout);35 while(cin>>Z>>I>>M>>L,Z||I||M||L)36 {37 memset(is_used,0,sizeof(is_used));38  L=(Z*L+I)%M;39  ans=0;40 while(is_used[L]==0)41 {is_used[L]=1;42 L=(Z*L+I)%M;43 ans++;44 }45 cout<<"Case "<<++T<<": "< <



模拟1下第一位可能不能循环所以。。。从第二位计算起就可以了~memset(a,0,sizeof(a)) 中间是0。。。这么次犯了这个错。。。下次就记住了。。。

转载地址:https://www.cnblogs.com/acmicpcstar/p/3689968.html 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

下一篇:UVAOJ 10061(未完结。续待)



[***.116.15.85]2023年03月16日 22时35分33秒