Могу ли я использовать неподписанные длинные длинные массивы

Я пытался решить эту проблему на хакерранке.

Вам дают четыре целых числа: N, S, P, Q. Вы будете использовать их для создания последовательности со следующим псевдокодом.

a[0] = S (modulo 2^31)
for i = 1 to N-1
a[i] = a[i-1]*P+Q (modulo 2^31)

Ваша задача — вычислить количество различных целых чисел в последовательности.

Sample Input

3 1 1 1
Sample Output

3

Constraints

1<= N <= 10^8
0<= S,P,Q < 2^31

И это было мое решение в c ++. В большинстве случаев я получал ошибки сегментации … Я знаю, что это должно было быть решено с помощью битовых массивов …, но хотел знать, почему это не работает.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;int main() {
unsigned long long n,s,p,q;

cin >> n >> s >> p >> q;

//declaring array to hold sequence
unsigned long long a[n];

// for loop termination
bool termination_check = true;

//initializing sequence
//s<2^31 hence, s modulo 2^31 is always s
a[0] = s;

//creating sequence
for(int i=1;i<n;i++){

//calculating next term of sequence..
a[i] = (a[i-1]*p)+q;

//since a[i] modulo 2^31 is a[i] when a[i] < 2^31
if(a[i]>=pow(2,31)){
a[i] = a[i]%31;

//when the current term matches with any of previous terms of sequence, then the
//terms just repeat after that (since p and q are constants)
for(int j=0;j<i;j++){
if(a[i]==a[j]){
cout <<i << endl;

//i was trying to use break but dont know why, it did not work
termination_check = false;
break;
break;
}
}
}
}

//if there was no termination of loop then all the terms are distinct
if(termination_check){
printf("%llu \n", n);
}

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}

-1

Решение

Да, вы можете иметь unsigned long long массивы в C ++. Но то, что у вас есть, не является массивом: unsigned long long a[n]; требует n быть константой. (Это было бы по-другому в C, но вы пишете C ++).

То, что он все еще работает, является расширением компилятора, которое позволяет смешивать C и C ++, но поведение не определено. Обработка ошибок, в частности, кажется, отсутствует.

0

Другие решения

Этот ответ был для предыдущей версии кода. Код теперь отредактирован внутри вопроса (j = i и i = n заменены двумя перерывами)

Посмотрите, что происходит, когда вы сталкиваетесь с делом

a[i] == a[j]

Ты устанавливаешь j в i, затем i в n, Но i меньше чем nтак что утверждение j<i остается верным. Затем цикл for продолжает работать, поэтому ваша программа пытается оценить

a[i] == a[j]

с новыми значениями, которые вы присвоили, вы на самом деле спрашиваете,

a[n] == a[i]

но если ваш массив a был массив размера nэто приводит к неопределенному поведению.

0

По вопросам рекламы [email protected]