Помогите решить задачу пожалуйста c++

Question

Помогите решить задачу пожалуйста c++

Рейтинг: -1Ответов: 1Опубликовано: 21.01.2023

Дано натуральное число, нужно его представить как произведение числе Фибоначчи больших 1. Вывести количество возможных вариантов разложения

#include <iostream>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n;
    cin >> n;

    for (long long i = 2; i * i <= n; ++i){
        while (n % i == 0){
            n /= i;
            cout << i << " ";
        }
    }

    if (n > 1)
        cout << n;
}

c# олимпиада

Источник: Stack Overflow на русском

Answer 1

▲ 1

Негде проверить, но посмотрите, не годится это решение? Для чисел до порядка 1Е18.

#include <vector>
#include <iostream>

using namespace std;

vector<long long> F = {2, 3};

long long countF(long long n, long long min = 0) {
    if (n == 1) return 1;

    if (min == F.size()) return 0;

    for (long long i = min; i < F.size(); ++i) {
        if (n % F[i] == 0) {
            return countF(n / F[i], i) + countF(n, i + 1);
            }
        }

    return 0;
    }


int main() {
    for (long long a = 2, b = 3; a < 2000000000000000000ll;) {
        long long c = a + b;
        F.push_back(c);
        a = b;
        b = c;
        }

    long long N;
    cin >> N;
    cout << countF(N);
    }

Для простых примеров, кажется, работает.

Помогите решить задачу пожалуйста c++

Ответы