题目链接

斐波那契

题目描述

给定斐波那契数列的定义：

给定两个整数 和 。要求在前 个斐波那契数中，找出包含数位 次数最多的那个数。如果存在多个斐波那契数并列次数最多，则输出其中数值最小的那个。

解题思路

本题的核心挑战在于处理斐波那契数列的巨大数值。斐波那契数列呈指数级增长，当 较大时（例如 ），其数值就会超出标准 64 位整型的表示范围。对于本题 的数据范围，我们必须使用高精度计算（或称大数运算）。

核心算法：高精度模拟

  1. 大数表示:

    处理大数的常用方法是将其表示为字符串。这样做既可以存储任意大的数字，也方便我们后续对每一位数字进行统计。

  2. 高精度加法:

    我们需要一个函数来模拟两个大数（字符串）的加法。这类似于我们手动做竖式加法的过程：

    • 将两个字符串翻转，以便从个位开始处理。
    • 逐位相加，同时维护一个进位 carry。
    • 将每一步计算结果的个位数追加到结果字符串中。
    • 循环结束后，处理最后的进位。
    • 将结果字符串再次翻转，得到最终的和。

  3. 迭代与比较:

    • 我们从 Fib_1 和 Fib_2 开始，使用高精度加法迭代地计算出前 个斐波那契数。
    • 在计算出每一个斐波那契数后，我们遍历其字符串表示，统计目标数位 的出现次数。
    • 我们维护两个变量：一个 max_count 记录当前为止最大的出现次数，另一个 result_fib 记录取得该最大次数的斐波那契数。
    • 当一个新计算出的斐波那契数 current_fib 的数位 出现次数 current_count 严格大于 max_count 时，我们才更新 max_count 和 result_fib。
    • 如果 current_count 等于 max_count，我们不做任何操作。这是因为题目要求在次数相同时输出最小的数，而我们是按顺序从小到大生成斐波那契数的，所以最先遇到的那个一定是最小的。

通过以上步骤，我们可以在 次迭代后找到最终的答案。

  • 语言特定实现: Java 的 BigInteger 类和 Python 的原生大整数支持可以极大地简化高精度计算部分，而 C++ 则需要我们手动实现字符串加法。

代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string big_add(string a, string b) {
    string res = "";
    int i = a.length() - 1, j = b.length() - 1, carry = 0;
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0';
        if (j >= 0) sum += b[j--] - '0';
        res += to_string(sum % 10);
        carry = sum / 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

int count_digit(const string& s, char d) {
    int count = 0;
    for (char c : s) {
        if (c == d) {
            count++;
        }
    }
    return count;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    char d_char;
    cin >> n >> d_char;

    if (n == 0) return 0;

    string a = "1", b = "1";
    int max_count = -1;
    string result_fib = "";

    if (n >= 1) {
        int count = count_digit(a, d_char);
        if (count > max_count) {
            max_count = count;
            result_fib = a;
        }
    }
    if (n >= 2) {
        int count = count_digit(b, d_char);
        if (count > max_count) {
            max_count = count;
            result_fib = b;
        }
    }

    for (int i = 3; i <= n; ++i) {
        string c = big_add(a, b);
        a = b;
        b = c;
        int count = count_digit(c, d_char);
        if (count > max_count) {
            max_count = count;
            result_fib = c;
        }
    }

    cout << result_fib << endl;

    return 0;
}

import java.util.Scanner;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int d = sc.nextInt();
        String d_str = String.valueOf(d);

        if (n == 0) return;

        BigInteger a = BigInteger.ONE;
        BigInteger b = BigInteger.ONE;
        int max_count = -1;
        BigInteger result_fib = BigInteger.ZERO;

        if (n >= 1) {
            int count = countDigit(a, d_str);
            if (count > max_count) {
                max_count = count;
                result_fib = a;
            }
        }
        if (n >= 2) {
            int count = countDigit(b, d_str);
             // Since a and b are the same for n=2, no need to check max_count again
             // but if definition was F_1=1, F_2=2, this would be needed.
            if (count > max_count) {
                max_count = count;
                result_fib = b;
            }
        }

        for (int i = 3; i <= n; i++) {
            BigInteger c = a.add(b);
            a = b;
            b = c;
            int count = countDigit(c, d_str);
            if (count > max_count) {
                max_count = count;
                result_fib = c;
            }
        }
        System.out.println(result_fib.toString());
    }

    private static int countDigit(BigInteger num, String d_str) {
        String s = num.toString();
        // A faster way than split or replace
        int count = 0;
        for(int i = 0; i < s.length(); i++) {
            if(s.substring(i, i+1).equals(d_str)) {
                count++;
            }
        }
        return count;
    }
}

import sys

def solve():
    try:
        n_str, d_str = sys.stdin.readline().split()
        n = int(n_str)
        
        if n == 0:
            return

        a, b = 1, 1
        max_count = -1
        result_fib = 0
        
        if n >= 1:
            count = str(a).count(d_str)
            if count > max_count:
                max_count = count
                result_fib = a
        
        if n >= 2:
            count = str(b).count(d_str)
            if count > max_count:
                max_count = count
                result_fib = b

        for i in range(3, n + 1):
            c = a + b
            a = b
            b = c
            count = str(c).count(d_str)
            if count > max_count:
                max_count = count
                result_fib = c
        
        print(result_fib)

    except (IOError, ValueError):
        pass

solve()

算法及复杂度

  • 算法: 高精度计算（大数运算）、模拟
  • 时间复杂度: 设 为第 个斐波那契数的位数。 的增长与 近似成正比。我们需要进行 次迭代，第 次迭代的主要操作是大数加法和数字统计，它们的复杂度都与 成正比。因此，总的时间复杂度为 。
  • 空间复杂度: 我们只需要存储前两个斐波那契数来计算下一个。最大的斐波那契数 的位数约为 。因此，空间复杂度为 。