循環節を探します

http://dmnotdm.cn/problem.php?id=1020

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
 
using namespace std;
 
long long t,n,m,k,pos[100005],a[100005],tmp;
 
int main()
{
    int i;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld%lld",&n,&m,&k);
        memset(pos,0,sizeof(pos));
        tmp=1;
        n%=k;
        for(i=1;i<=m;i++)
        {
            tmp=(tmp*n)%k;
            if(!pos[tmp])   pos[tmp]=i;
            else break;
            a[i]=tmp;
        }
        if(i>m)      printf("%lld
",tmp);
        else
        {
            m-=(pos[tmp]-1);
            m%=(i-pos[tmp]);
            if(!m)  m=i-pos[tmp];
            m--;
            printf("%lld
",a[pos[tmp]+m]);
 
        }
    }
    return 0;
}

http://acm.hdu.edu.cn/showproblem.php?pid=1005

#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;

int rec[60];

int main()
{
    int a, b, n;
    rec[0] = rec[1] = rec[2] = 1;
    while( scanf( "%d %d %d", &a, &b, &n ), a | b | n )
    {
        int beg, end, flag = 0;
        for( int i = 3; i <= n && !flag; ++i )
        {
            rec[i] = ( a * rec[i-1] + b * rec[i-2] ) % 7;
            for( int j = 2; j <= i - 1; ++j )
            {
                if( rec[i] == rec[j] && rec[i-1] == rec[j-1] )
                {
                    beg = j, end = i;
                    flag = 1;
                    break;
                }
            }
        }
        if( flag )
        {
            printf( "%d
", rec[beg+(n-end)%(end-beg)] );
        }
        else
            printf( "%d
", rec[n] );
    }
    return 0;
}