ACM 374 Big Mod

算mod，但慢慢來是會TL的。
所以要想個比較快的方法。

因為mod的值一定會重複，
所以就把mod值紀錄起來，
每次有新mod值進來就加進去，
如果mod已經被紀錄了，表示重複，
輸出紀錄值即可。

/* ACM 374 Big Mod
 * mythnc
 * 2011/10/31 11:57:08   
 * run time: 0.02
 */
#include <stdio.h>

#define MAXARY 47000
#define IN     1
#define OUT    0

int add(int *, int, int *);

int main(void)
{
    int b, p, m, tmp, tag, count;
    int rec[MAXARY];

    while (scanf("%d %d %d", &b, &p, &m) == 3) {
        count = 0;
        tag = OUT;
        for (rec[count++] = tmp = b %= m; --p;) {
            b *= tmp;
            if (b > m)
                b %= m;
            if (add(rec, b, &count) == IN) {
                tag = IN;
                break;
            }
        }

        if (tag == IN) {
            tmp = p % count - 1;
            /* can be divide */
            if (tmp < 0)
                tmp = count - 1;
            printf("%d\n", rec[tmp]);
            continue;
        }

        printf("%d\n", b);
    }
    return 0;
}

/* add: save mod number in rec,
 * if number is already in rec,
 * return IN,
 * else save it return OUT */
int add(int *rec, int b, int *n)
{
    int i;

    for (i = 0; i < *n; i++)
        if (rec[i] == b)
            return IN;

    rec[(*n)++] = b;
    return OUT;
}