The second approach is not workable.Adrian Kuegel wrote:The description of the solutions for the problems are now online.
You can read them at http://www.informatik.uni-ulm.de/acm/Lo ... judge.html .
I use the STL set and I have highly optimized my code, but it is still TLE...Another possibility is to store the numbers of the soldiers in a set and when we calculate a number which is already in the set, we have found the first soldier to commit suicide.
A good hashtable is faster than that -- O(1), on average.I even take a read on the O(log log n)-query-time van Emde Boas tree.
Code: Select all
#include <iostream>
#include <cstring>
#include <map>
using namespace std;
long long int n, a, b;
char seen [ 1000000000 ];
int ind [ 1000000 ];
int rem;
void process();
int main()
{
cin >> n;
while ( n != 0 )
{
cin >> a >> b;
process();
cin >> n;
}
return 0;
}
void process()
{
memset( seen, 0, sizeof(seen) );
long long int next = 0;
int cnt = 0 ;
while ( true )
{
if ( seen[ next ] == 0 )
{
seen[ next ] = 1;
ind[ cnt++ ] = next;
}
else
{
for ( int i = 0; i < cnt; i++ )
{
if ( ind[ i ] == next )
{
rem = n - (cnt - i);
break;
}
}
break;
}
next = (((a * ((next * next) % n)) % n) + b) % n;
}
cout << rem << endl;
}