Any sequence of form <next number> = f(<previous number>) mod M is always periodic, simply because there are just M possible numbers (0..M-1), and once any number repeats, the sequence will repeat from that point forward, too. However, some initial part of the sequence (called 'pre-cycle') might not appear in its cyclic part.The cycle might not begin with the seed
Just now i got AC, where i considered that L is less than M.wfuny wrote:L might bigger than M
add L=L%M in your code
I hope it can help you.
Code: Select all
initialize count=1;
loop
// calculate next 'l' using formula.
// check whether it is repeated and break if so.
// Else count++.
end loop
if ( repeated_number == seed )
print count;
else
print (count-1);
I don't understand why it will modify the output...ExUCI wrote:The only thing wrong is that you have to generate first a random number and then start your calculations
Remove you code after AC
Code: Select all
Removed after AC
L might not be less than M
Critical Input:
1111 1111 1111 1111
9999 9999 9999 9999
9876 5432 1234 1786
1234 5678 8956 8524
9999 1111 9999 1111
Critical Output:
Case 1: 1
Case 2: 1
Case 3: 77
Case 4: 373
Case 5: 1
From http://tausiq.wordpress.com/2009/01/24/acm-uva-350/
Code: Select all
#include<cstdio>
#include<cstring>
#include<cstdlib>
int main(){
int *a;
int z,l,i,m,count,sum,count2=0;
while(scanf("%d %d %d %d", &z,&i,&m,&l),!(z==0 && i==0 && m==0 && l==0)){
a = (int*)malloc(sizeof(int)*10000);
memset(a,0,sizeof(a));
count=1; count2++;
while(a[l]==0){
a[l]=count++;
l = ((z*l)+i)%m;
}
printf("Case %d: %d\n", count2, count-a[l]);
free(a);
}
return 0;
}
Code: Select all
#include<cstdio>
#include<cstring>
#include<cstdlib>
int main(){
int *a;
int z,l,i,m,count,sum,count2=0;
while(scanf("%d %d %d %d", &z,&i,&m,&l),!(z==0 && i==0 && m==0 && l==0)){
a = (int*)malloc(sizeof(int)*10000);
memset(a,0,sizeof(a));
count=1; count2++;
while(a[l]==0){
a[l]=count++;
l = ((z*l)+i)%m;
}
printf("Case %d: %d\n", count2, count-a[l]);
free(a);
}
return 0;
}