Uva 11582 Colossal Fibonacci Numbers! (循环节、幂取模、打表)
The i’th Fibonacci number f(i) is recursively defined in the following way:
• and
•for every
Your task is to compute some values of this sequence.
Input
Input begins with an integer , the number of test cases.
Each test case consists of three integers a, b, n where
(a and b will not both be zero) and .
Output
For each test case, output a single line containing the remainder of f() upon division by n
Sample Input
3
1 1 2
2 3 1000
18446744073709551615 18446744073709551615 1000
Sample Output
1
21
250
ps: 这题数据非常大,必须通过找循环节来解决,,当f(i), f(i+1)与前面的数相同时,就会开始产生循环节。因为余数最多n种,所以最多项就会出现重复。鉴于数据规模实在过于庞大(),单纯靠每次找循环节和快速幂会造成TLE(我上交tle了(,,•́ . •̀,,) ), 所以还需要将1~1000取模的所有情况打表,就是记录他们的循环节。
TLE code:
#include<iostream>
using namespace std;
const int maxn = 1e6+10;
int fib[maxn];
int pow(unsigned long long a, unsigned long long b, int c)
{//幂取模 a^b % c
int ans = 1;
a = a % c;
while(b > 0)
{
if(b & 1) ans = ((a % c) * (ans % c)) % c;
a = (a * a) % c;
b = b >> 1;
}
return ans;
}
int main()
{
//虽然双加速但也超时
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin>>n;
unsigned long long a, b;
int c;
while(n--)
{
cin>>a>>b>>c;
int maxt = c * c + 4;
fib[0] = 0 , fib[1] = 1;
for(int i = 2; i < maxt; i++)fib[i] = (fib[i - 1] % c + fib[i - 2] % c) % c;
int temp = 1;
for(int i = 2; i < maxt; i++){
if(fib[0] == fib[i] && fib[1] == fib[i+1])
{
temp = i;
break;
}
}
int tt = pow(a, b, temp);
if(a == 0 || c == 1)cout<<0<<endl;
else cout<<fib[tt % temp]<<endl;
}
return 0;
}
改好后:
#include<iostream>
#include<vector>
using namespace std;
vector<int> fib[1004];//保存循环节
void init()
{//打表保存循环节
for(int i = 2; i <= 1000; i++)
{
int mod = i;
int a = 0, b = 1;
int c = (a + b) % mod;
fib[i].push_back(a);
fib[i].push_back(b);
fib[i].push_back(c);
while(!(b == 0 && c == 1))
{
a = b;
b = c;
c = ((a % mod) + (b % mod)) % mod;
fib[i].push_back(c);
}
fib[i].pop_back();
fib[i].pop_back();
}
}
int pow(unsigned long long a, unsigned long long b, int n)
{//幂取模
int ans = 1;
while(b > 0)
{
if(b & 1)ans = ((a % n) * (ans % n)) % n;
a = ((a % n) * (a % n)) % n;
b = b >> 1;
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
init();
while(T--)
{
unsigned long long a, b;
int n;
cin>>a>>b>>n;
if(a == 0 || n == 0){//f(0) = 0
cout<<0<<endl;
continue;
}
int t = pow(a, b, fib[n].size());
cout<<fib[n][t]<<endl;
}
return 0;
}
上一篇: 展讯平台手机重启问题分析指南