Подсчитайте последовательность, в которой gcd ​​равен 1 - PullRequest
Новая
       31

Подсчитайте последовательность, в которой gcd ​​равен 1

0 голосов
/ 14 октября 2019

У меня возникла проблема с вопросом:

enter image description here

, и это пример ввода и вывода:

enter image description here

IЯ стараюсь изо всех сил, чтобы решить эту проблему, это мой код: 

#include <iostream>
#include <cmath>


using namespace std;

unsigned long long FindGCD(unsigned long long a, unsigned long long b)
{
    if (a==0)
        return b;
    else
        return FindGCD(b%a, a);
}

unsigned long long FindIndex(unsigned long long objective, unsigned long long l, unsigned long long r, unsigned long long arr[])
{
    for (int i = l; i <= r; ++i)
    {
        if (arr[i]==objective)
            return i;
    }

    return -1;
}

int main()
{
    // user input : the number of integers
    unsigned long long n;
    cin>>n;

    // user input : integers in array
    unsigned long long arr[n];
    for (unsigned long long i = 0; i < n; ++i)
        cin>>arr[i];

    // start to find all tuple
    unsigned long long tuple_count = 0;

    // record the index of one
    unsigned long long index_of_one = -2;

    for (unsigned long long l = 0; l < n; ++l)
    {
        // consider if arr[l] is 1
        if (arr[l]==1)
            tuple_count += n-l;
        else
        {
            if (l>index_of_one && index_of_one != -1)
                index_of_one = FindIndex(1,l+1,n-1,arr);

            // if there is 1 after
            if (index_of_one!=-1 && index_of_one!=-2)
            {
                tuple_count += n-index_of_one;

                unsigned long long temp = arr[l];

                for (unsigned long long i = l+1; i < index_of_one; ++i)
                {
                    temp = FindGCD(temp,arr[i]);

                    if (temp==1)
                    {
                        tuple_count += index_of_one-i;
                        break;
                    }
                }
            }
            else
            {
                unsigned long long temp = arr[l];

                for (unsigned long long i = l+1; i < n; ++i)
                {
                    temp = FindGCD(temp,arr[i]);

                    if (temp==1)
                    {
                        tuple_count += n-i;
                        break;
                    }
                }

            }
        }
    }

    // output
    cout<<tuple_count<<endl;

    //system("Pause");
    return 0;
}

Мысль: чтобы быстро сосчитать кортеж, я сосредоточился на поиске «1», потому что gcd любой последовательности, включая одну, равен 1. После нахождения ближайшего 1 из текущего номера, я считаю количество последовательностей между текущим номером и ближайшим "1".

Легко найти gcd последовательности. Если gcd последовательности равен 1, цикл for останавливается, поскольку все оставшиеся числа, добавленные в последовательность, будут генерировать gcd = 1, поэтому мне не нужно вычислять.

Код работает отлично в большинстве случаев. Однако в некоторых особых и неизвестных случаях я получаю «TLE».

Я хочу ускорить мой алгоритм, кто может мне помочь? Должен ли я изменить совершенно другой способ решения проблемы?

Кто-нибудь может мне помочь?

пс. Я не хочу код, некоторые практические советы достаточно!

...