UVa-11582：Colossal Fibonacci Numbers!（模算术）

这是个开心的题目，因为既可以自己翻译，代码又好写ヾ(๑╹◡╹)ﾉ"

The i’th Fibonacci number f(i) is recursively deﬁned in the following way:

• f(0) = 0 and f(1) = 1

• f(i + 2) = f(i + 1) + f(i) for every i ≥ 0

Your task is to compute some values of this sequence.

Input

Input begins with an integer t ≤ 10,000, the number of test cases. Each test case consists of three integers a, b, n where 0 ≤ a,b < 2⁶⁴ (a and b will not both be zero) and 1 ≤ n ≤ 1000.
Output
For each test case, output a single line containing the remainder of f(ab) upon division by n.

Sample Input
3

1 1 2

2 3 1000

18446744073709551615 18446744073709551615 1000

Sample Output
1

250

概译：对于斐波那契数列f = {0，1，1，2……}，给出n，f数列的所有项都%=n，还给了a和b，求f[a^b]等于几。

思路：

发现a和b极大所以肯定是找规律了

--> 斐波那契是固定的那循环长度应该跟n有关

--> 余数最多有n种，（注意序列是0，1开头），则最坏情况下n个数以后又爆出0

--> 斐波那契数列只要确定两个数则后面的序列都是确定的，确定了0以后，0后面那个数一旦确定则循环节就确定了

--> 最坏情况，0的后面n次以后爆出1

--> 故在n²个数以内必出循环节，n²的暴力还是可以承受的，找一下循环节长度L，输出f[a^b%L（快速幂）]

PS：不妨简单证明一下0的后面最坏n次以后必爆1.

假如序列会发生：01abc，02xyz，02xyz，01……这种情况，则由于非1数字先行重复了，会导致我们未必在n次以内捕获数字1.但这种情况真的会存在吗？

--> 如果真的存在了，由于z+0=2，所以一旦02循环，则02将成为永远的循环节，不会再出现01了，只会有01abc，02xyz，02xyz，02xyz，……

--> (c+0)%n=2，c又在0~n之内，c=2=z

--> (b+c)%n=0，b又在0~n之内，b=n-2=y

--> ……以此类推，01何以创造02帝国？

--> 矛盾。故斐波那契一定是以01开头的循环节，n次内必爆1.

声明：由于紫书和题解们都是一笔描过n²内可求解，故上述想法为个人脑洞，欢迎纠错与讨论。

50ms

 #include <bits/stdc++.h>

 using namespace std;

 typedef unsigned long long ull;

 int test, n, f[]={,};

 ull a, b;

 ull qpow(ull a, ull b, int mod)//为了防爆ull，a传入a%mod

 {

     ull ans = ;

     while (b)

     {

         if (b% == )    ans = ans*a%mod;

         a = a*a%mod;

         b >>= ;

     }

     return ans;

 }

 int main()

 {

     scanf("%d", &test);

     while (test--)

     {

         int record = ;

         scanf("%llu%llu%d", &a, &b, &n);

         //寻找循环节

         //也可以把f开成f[maxn][maxn*maxn+5]在test循环之前预处理

         //如果预处理的话这里直接O（1）查询了，空间换时间吧

         for (int i = ; i <= n*n + ; i++)

         {

             f[i] = (f[i-] + f[i-]) % n;

             if (f[i] ==  && f[i-] == )

             {

                 record = i-;//循环节长度

                 break;

             }

         }

         printf("%d\n", n ==  ?  : f[qpow(a%record, b, record)]);

     }

 }

再贴一个预处理的标程：

20ms

 // UVa11582 Colossal Fibonacci Numbers!

 // Rujia Liu

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 const int maxn =  + ;

 typedef unsigned long long ULL;

 int f[maxn][maxn*], period[maxn];

 int pow_mod(ULL a, ULL b, int n) {

   if(!b) return ;

   int k = pow_mod(a, b/, n);

   k = k * k % n;

   if(b % ) k = k * a % n;

   return k;

 }

 int solve(ULL a, ULL b, int n) {

   if(a ==  || n == ) return ; // attention!

   int p = pow_mod(a % period[n], b, period[n]);

   return f[n][p];

 }

 int main() {

   for(int n = ; n <= ; n++) {

     f[n][] = ; f[n][] = ;

     for(int i = ; ; i++) {

       f[n][i] = (f[n][i-] + f[n][i-]) % n;

       if(f[n][i-] ==  && f[n][i] == ) {

         period[n] = i - ;

         break;

       }

     }

   }

   ULL a, b;

   int n, T;

   cin >> T;

   while(T--) {

     cin >> a >> b >> n;

     cout << solve(a, b, n) << "\n";

   }

   return ;

 }

至于为什么标程的二维f数组只开到maxn*6……我打了个表，最长是n=750时循环节3000~

巴特西

UVa-11582：Colossal Fibonacci Numbers!（模算术）

最新文章

热门文章