內容
給你 n,m,求 gcd(Fm,Fn)
*Fx 代表 Fibonacci 數列第 x 項
2019/6/8 時限調降至 0.5s
輸入
輸入有多行
每行有 m,n 兩數(m,n<=10000)
1 2
3 6
輸出
答案(保證可以用 unsigned long long 存)
1
2
解題思路
假設要求 GCD(f(25),f(20))，先展開 f(25)
= [1 * f(25-1)] + [1 * f(25-2)] ( f(m-1) = f(m-2) + f(m-3) )
= [2 * f(25-2)] + [1 * f(25-3)]
= [3 * f(25-3)] + [2 * f(25-4)] ( 2 * f(m-2) = [2 * ( f(m-3) + f(m-4) )] = 2 * f(m-3) + 2 * f(m-4) )
= [5 * f(25-4)] + [3 * f(25-5)]
= [8 * f(25-5)] + [5 * f(25-6)]
這時候可以發現兩件事
觀察*號左邊發現剛好會是費式數列，所以轉換成公式
f(m) = [f(m-n+1) * f(n)] + [f(m-n) * f(n-1)]
所以上面的式子就能轉換成 [f(6) * f(20)] + [f(5) * f(19)]
8 * f(20) 必為 f(20) 倍數，所以不必討論，也就是說接下來只需討論 '+' 右側的 f(5) * f(19) 和 f(20) 的最大功倍數，而此時因為 f(n) 和 f(n-1) 必定互質的關係 f(19) 也不必討論，只要求 GCD(f(5) , f(20)) 即可。
把以上兩個結論總和成一個公式 :
GCD(f(m) , f(n)) = GCD(f(m-n) , f(n))
然後發現每次轉換都會得到一組比較小的 GCD(f(m),f(n))，所以繼續用開頭的方式轉換新的 GCD(f(5),f(20))
展開 f(20) = [f(16) * f(5)] + [f(15) * f(4)]
轉換後變成 : GCD((f(15) , f(5))
展開 f(15) = [f(11) * f(5)] + [f(10) * f(4)]
轉換後變成 : GCD(f(10) , f(5))
展開 f(10) = [f(6) * f(5)] + [f(5) * f(4)]
轉換後變成 : GCD(f(5) , f(5)) = f(5) = 5
然後就會發現 GCD(f(m),f(n)) 就是再求 f(GCD(m,n))…
而題目保證答案可以用 unsigned long long 存，而費式數列第 94 項會超出 unsigned long long 的範圍，所以先建好 1~93 的費式數列表，之後查 F[GCD(m,n)] 輸出即可。
完整程式碼
正常版
AC (40ms, 88KB)
#include <stdio.h>
#define SWAP(x, y) (x)^=((y)^=((x)^=(y)))
#define MAX 94
unsigned long long F[MAX] = { 0, 1 };
inline int GCD(int n, int m)
{
while (n)
{
m %= n;
SWAP(m, n);
}
return m;
}
int main()
{
int m, n;
for (int i = 2; i < MAX; ++i)
F[i] = F[i - 1] + F[i - 2];
while (scanf(" %d %d", &m, &n) == 2)
printf("%llu\n", F[GCD(m, n)]);
return 0;
}
|
AC (15ms, 1MB)
IO 優化版
#include <stdio.h>
#define SWAP(x, y) (x)^=((y)^=((x)^=(y)))
#define MAX 94
#define BUFSIZ 1048576
unsigned long long F[MAX] = { 0, 1 };
inline char readChar()
{
static char buffer[BUFSIZ], * now = buffer + BUFSIZ, * end = buffer + BUFSIZ;
if (now == end)
{
if (end < buffer + BUFSIZ)
return EOF;
end = (buffer + fread(buffer, 1, BUFSIZ, stdin));
now = buffer;
}
return *now++;
}
inline char readUInt(unsigned int* dst)
{
register char ch;
while ((ch = readChar()) < '0')
if (ch == EOF) return 0;
*dst = ch ^ '0';
while ((ch = readChar()) >= '0')
* dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
return 1;
}
inline void putULongLong(register unsigned long long src, const char suffix)
{
register unsigned long long div;
char buffer[22], * st = buffer + 20;
*st = suffix, * (st + 1) = 0;
do
{
*(--st) = src - ((div = src / 10) << 3) - (div << 1) + '0';
} while (src = div);
fputs(st, stdout);
}
inline int GCD(int n, int m)
{
while (n)
{
m %= n;
SWAP(m, n);
}
return m;
}
int main()
{
int m, n;
for (int i = 2; i < MAX; ++i)
F[i] = F[i - 1] + F[i - 2];
while (readUInt(&n), readUInt(&m))
putULongLong(F[GCD(m, n)], '\n');
return 0;
}
|
