首页 > 代码库 > UVA 11582 Colossal Fibonacci Numbers! 数学
UVA 11582 Colossal Fibonacci Numbers! 数学
n比较小,最多n*n就回出现循环节....
Colossal Fibonacci Numbers!
Description Problem F: Colossal Fibonacci Numbers!The i‘th Fibonacci number f (i) is recursively defined in the following way:
Your task is to compute some values of this sequence. Input begins with an integer t a‰¤ 10,000, the number of test cases. Each test case consists of three integers a,b,nwhere 0 a‰¤ a,b < 264 (a and b will not both be zero) and 1 a‰¤ n a‰¤ 1000. For each test case, output a single line containing the remainder of f (ab) upon division by n. Sample input3 1 1 2 2 3 1000 18446744073709551615 18446744073709551615 1000 Sample output1 21 250 Zachary Friggstad Source Root :: AOAPC II: Beginning Algorithm Contests (Second Edition) (Rujia Liu) :: Chapter 10. Maths :: Examples Root :: Prominent Problemsetters :: Zachary Friggstad
|
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef unsigned long long int uLL; uLL d[2000200],dn; uLL A,B,M; uLL quickpow() { uLL e=1; A=A%dn; while(B) { if(B%2) { e=(e*A)%dn; } A=(A*A)%dn; B/=(uLL)2; } return e; } int main() { int T_T; cin>>T_T; while(T_T--) { dn=0; cin>>A>>B>>M; if(M==1) { puts("0"); continue; } uLL a=(uLL)1,b=(uLL)1; uLL la=a,lb=b; d[dn++]=a;d[dn++]=b; while(true) { a=(la+lb)%M; b=(lb+a)%M; if(d[0]==a&&d[1]==b) break; d[dn++]=a;d[dn++]=b; la=a; lb=b; } cout<<d[quickpow()-1]<<endl; } return 0; }
UVA 11582 Colossal Fibonacci Numbers! 数学
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。