부호없는 긴 long 배열을 사용할 수 있습니까?

Question

해커 클랜에서이 문제를 해결하려고했습니다.

네 개의 정수 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; 
} 

Answer 1

예, C 배열에 unsigned long long 개의 배열을 포함 할 수 있습니다. 하지만 가지고있는 것은 배열이 아닙니다 : unsigned long long a[n];은 n이 상수가되어야합니다. (이것은 C와는 다르지만 C++을 쓰고 있습니다.)

여전히 실행되는 것은 C 및 C++을 혼합 할 수있는 컴파일러 확장이지만 동작은 정의되지 않습니다. 특히 오류 처리가 부족한 것 같습니다.

Answer 2

이 답변 코드의 이전 버전이었다. 이 코드는 이제 질문 (J = i와 난 = n은 두 휴식으로 대체)

당신이 다음 j에 i 설정 i

a[i] == a[j] 

경우를 만날 때 무슨 일이 happends 참조 내부 편집 한 n. 그러나 i은 n보다 작으므로 j<i 문은 true로 유지됩니다. 루프 후들이받은 계속 당신, 그래서 당신을 programm 당신이 할당 된 새 값으로

a[i] == a[j] 

을 평가하려고, 당신은 실제로 요구하는 경우

a[n] == a[i] 

하지만 배열 a 크기 n의 배열 인 경우 , 이는 정의되지 않은 동작을 초래합니다.