UVA 11582 Colossal Fibonacci Numbers(数学)-白红宇

UVA 11582 Colossal Fibonacci Numbers(数学)

阅读量：5144 次

发布时间：2019-06-13

本文共 1509 字，大约阅读时间需要 5 分钟。

Colossal Fibonacci Numbers

想先说下最近的状态吧,已经考完试了,这个暑假也应该是最后刷题的暑假了,打完今年acm就应该会退了,但是还什么都不会呢? +_+ 所以这个暑假,一定要竭尽全力地去刷题,当然,也是能好好刷题的最后时间了.

【题目链接】

【题目类型】数学

&题意：

求Fi(f(a^b)%n) Fi()是斐波那契

&题解：

注意:unsigned时要把%d全换成%u

数学大法好. 首先你要能看出来这是有循环节的,因为f(i)=f(i-1)+f(i-2) 那么只要f(i-1),f(i-2)和以前出现过的f(x-1),f(x-2)对应相等,那么就答案就一定会出现循环.而且循环节长度不会超过1000x1000,因为取余后一共有1000种情况,那个连着的2个在一起就是1000x1000

之后,打个表,做一次快速幂,对循环节取余,就可以a了.

&代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              using namespace std;#define INF 0x3f3f3f3f#define ull unsigned long long#define fo(i,a,b) for(int i=(a);i<=(b);i++)#define fd(i,a,b) for(int i=(a);i>=(b);i--)#define cle(a,v) memset(a,(v),sizeof(a))const int maxn = 1e3 + 7;int t, n, cycle[maxn];ull a, b;vector
              
                tab[maxn];void pre() { for(int i = 2; i <= 1000; i++) { tab[i].push_back(0); tab[i].push_back(1); for(int j = 2;; j++) { tab[i].push_back((tab[i][j - 1] + tab[i][j - 2]) % i); if(tab[i][j] == 1 && tab[i][j - 1] == 0) { cycle[i] = j - 1; break; } } }}int pow(ull a, ull b, int m) { int ans = 1; while(b) { if(b & 1) ans = (ans * a) % m; a = (a * a) % m; b >>= 1; } return ans;}int main() { freopen("E:1.in", "r", stdin); pre(); scanf("%d", &t); while(t--) { scanf("%llu%llu%d", &a, &b, &n); if(a == 0 || n == 1) printf("0\n"); else printf("%d\n", tab[n][pow(a % cycle[n], b, cycle[n]) % cycle[n]]); } return 0;}

转载于:https://www.cnblogs.com/s1124yy/p/7087223.html

你可能感兴趣的文章