uva 11582 Colossal Fibonacci Numbers! (フィボナッチ型除去周期性)

メーターを打つことでフィボナッチ数列がある数を模除した結果は一定の周期性を示すことが分かった.
数列のある数は前の2つの数に依存し、ある数と次の数のモジュール除去結果がf 0 f 1と同じである場合、すなわち新しい周期が開始される.
最初の2つの数に依存して1つの数モードごとにnを除去することはnの可能性があり、2つの数はnである.×n、すなわち、ループセクションの要素はnを超えない×n;
先に表を打ってnが1～1000の周期数ごとに打ち出して、a^b%(iごとに対応する周期数)、高速べき乗で型を除いて、型を除いた結果<=n、直接求めればいい

#include 
#include 
using namespace std;
const int maxn=1e6+10;
int q[maxn];
int  ss[maxn];
int sto[1010];
typedef unsigned long long ll;
void ser()
{
    sto[1]=1;
    for (int j=2;j<=1000;j++)
    {
      q[0]=0%j;q[1]=1%j;
      for (int i=2;i<=j*j;i++)
      {
      q[i]=(q[i-1]%j+q[i-2]%j)%j;
      if (q[i]==1&&q[i-1]==0)
      {
         sto[j]=i-1;
         break;
      }
      }
    }
}
ll mi(ll a,ll b,ll c)
{
    ll ans=1;
    a=a%c;
    while (b!=0)
    {
       if (b&1) ans=(ans*a)%c;
       b>>=1;
       a=(a*a)%c;
    }
    return ans;
}
int main()
{
   int t;
   ll a,b,c;
   ser();
   cin>>t;
   while (t--)
   {
     scanf("%llu%llu%llu",&a,&b,&c);//unsigned long long     
     int len=sto[c];
     ll cnt=mi(a,b,len);
     ss[0]=0%c;ss[1]=1%c;
     for (int i=2;i<=cnt;i++) ss[i]=(ss[i-1]+ss[i-2])%c;
     if (a==0&&b==0) printf("0
");
     else
     printf("%d
",ss[cnt]);
   }
   return 0;
}