2011-09-24 20:28:53Morris
d271. 11582 - Colossal Fibonacci Numbers!
d271. 11582 - Colossal Fibonacci Numbers!
/**********************************************************************************/
/* Problem: d271 "11582 - Colossal Fibonacci Numbers!" from UVA11582 */
/* Language: C (1445 Bytes) */
/* Result: AC(24ms, 6MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-09-24 20:13:04 */
/**********************************************************************************/
#include<stdio.h>
#include<math.h>
#include<string.h>
int mark[1000000], Q[1000000], Qt;
int F[1000001];
struct state{
int tail, cycle, start;
}K[1001];
int POW(unsigned long long x, unsigned long long y, int mod) {
int Ans = 1, t = x%mod;
while(y) {
if(y&1) {
Ans *= t%mod, Ans %= mod;
}
t *= t%mod, t %= mod;
y = y/2;
}
return Ans;
}
int Build() {
int k, i, total = 0, t, tail, cycle;
memset(mark, -1, sizeof(mark));
for(k = 1; k <= 1000; k++) {
K[k].start = total, Qt = 0;
for(i = 0; ; i++) {
if(i < 2) F[i+total] = i%k;
else F[i+total] = (F[i-1+total] + F[i-2+total])%k;
t = F[i+total];
if(i >= 1) t += F[i-1+total]*1000;
if(mark[t] != -1) {
tail = mark[t], cycle = i - tail;
break;
}
mark[t] = i;
Q[Qt++] = t;
}
tail--;
K[k].tail = tail, K[k].cycle = cycle;
total += i;
for(i = 0; i < Qt; i++)
mark[Q[i]] = -1;
}
}
main() {
Build();
int n, i, j, T;
unsigned long long a, b;
scanf("%d", &T);
while(T--) {
scanf("%llu %llu %d", &a, &b, &n);
int tail, cycle, start;
tail = K[n].tail, cycle = K[n].cycle, start = K[n].start;
int Ans;
if(b*log10(a) <= log10(tail))
Ans = F[(int)(pow(a, b))+start];
else {
int tmp;
tmp = POW(a, b, cycle);
if(tmp == 0) tmp += cycle;
tmp = ((tmp - tail)%cycle+cycle)%cycle + tail;
Ans = F[tmp+start];
}
printf("%d\n", Ans);
}
return 0;
}
內容 ：
費式數列的遞迴關係式的定義如下:
f (0) = 0 and f (1) = 1
f (i+2) = f (i+1) + f (i) for every i ≥ 0
你的工作就是對於這個數列計算一些值
輸入說明
：
第一行代表幾組測資 t ≤ 10,000,
每組有三個數字a,b,n,其範圍 0 ≤ a,b < 264(a,b,不同時為0)，以及 1 ≤ n ≤ 1000.
輸出說明
：
對於每一個測資，印出一行 f (ab) 除以n的餘數
範例輸入 ：
3 1 1 2 2 3 1000 18446744073709551615 18446744073709551615 1000
範例輸出 ：
1 21 250
提示
：
出處
：
/**********************************************************************************/
/* Problem: d271 "11582 - Colossal Fibonacci Numbers!" from UVA11582 */
/* Language: C (1445 Bytes) */
/* Result: AC(24ms, 6MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-09-24 20:13:04 */
/**********************************************************************************/
#include<stdio.h>
#include<math.h>
#include<string.h>
int mark[1000000], Q[1000000], Qt;
int F[1000001];
struct state{
int tail, cycle, start;
}K[1001];
int POW(unsigned long long x, unsigned long long y, int mod) {
int Ans = 1, t = x%mod;
while(y) {
if(y&1) {
Ans *= t%mod, Ans %= mod;
}
t *= t%mod, t %= mod;
y = y/2;
}
return Ans;
}
int Build() {
int k, i, total = 0, t, tail, cycle;
memset(mark, -1, sizeof(mark));
for(k = 1; k <= 1000; k++) {
K[k].start = total, Qt = 0;
for(i = 0; ; i++) {
if(i < 2) F[i+total] = i%k;
else F[i+total] = (F[i-1+total] + F[i-2+total])%k;
t = F[i+total];
if(i >= 1) t += F[i-1+total]*1000;
if(mark[t] != -1) {
tail = mark[t], cycle = i - tail;
break;
}
mark[t] = i;
Q[Qt++] = t;
}
tail--;
K[k].tail = tail, K[k].cycle = cycle;
total += i;
for(i = 0; i < Qt; i++)
mark[Q[i]] = -1;
}
}
main() {
Build();
int n, i, j, T;
unsigned long long a, b;
scanf("%d", &T);
while(T--) {
scanf("%llu %llu %d", &a, &b, &n);
int tail, cycle, start;
tail = K[n].tail, cycle = K[n].cycle, start = K[n].start;
int Ans;
if(b*log10(a) <= log10(tail))
Ans = F[(int)(pow(a, b))+start];
else {
int tmp;
tmp = POW(a, b, cycle);
if(tmp == 0) tmp += cycle;
tmp = ((tmp - tail)%cycle+cycle)%cycle + tail;
Ans = F[tmp+start];
}
printf("%d\n", Ans);
}
return 0;
}