我可以使用 unsigned long long 数组吗

Question

我试图在 hackerrank 上解决这个问题。

给你四个整数：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

这个答案是针对以前版本的代码。现在已经在问题中编辑了代码（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 的数组，这会导致未定义的行为。

Answer 2

是的，您可以在 C++ 中使用 unsigned long long 个数组。但是您拥有的不是数组：unsigned long long a[n]; 要求 n 是一个常量。（这在 C 中会有所不同，但您正在编写 C++）。

它仍然运行是一个编译器扩展，它允许您混合使用 C 和 C++，但行为未定义。似乎特别缺乏错误处理。

我可以使用 unsigned long long 数组吗

Can i use unsigned long long arrays

c++

bitarray

unsigned-long-long-int