Poj Solution 2939

http://poj.org/problem?id=2939

#include <algorithm>
#include <cstdio>
#include <string.h>
#include <map>
#include <stack>
#include <memory.h>
#include <math.h>
#include <queue>
using namespace std;
#define count dofudf
const int prime = 3374521;
int hash[prime] = { 0 };
int num[prime];
int id[prime];
int count = 0;

int get( int x ) {
    int y = x%prime;
    while( hash[y] == count && num[y] != x ) {
        y++;
        if( y == prime )
            y = 0;
    }
    return y;
}
        

int main( ) {
    int a, b, n, i, k;
    long long x;

    while( scanf( "%d%d%d", &n, &a, &b ) == 3 ) {
        if( n < 0 )
            break;
        x = 0;
        count++;
        i = 0;
        a%=n, b%=n;
        while( hash[k=get(int(x))] < count ){
            num[k] = x;
            id[k] = i;
            hash[k] = count;
            x = (a*x%n*x+b) % n;
            i++;
        }
        printf( "%dn", n-(i-id[k]) );
    }
    return 0;
}



											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *