-1

我试图在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;
}
4

2 回答 2

0

此答案适用于以前版本的代码。代码现在已在问题中进行了编辑（j = i 和 i = n 被两个中断替换）

看看你遇到这个案子的时候会发生什么

a[i] == a[j]

您设置j为i，然后设置i为n。Buti小于n，所以该陈述j<i仍然成立。然后您的 for 循环继续运行，因此您的程序尝试评估

a[i] == a[j]

使用您分配的新值，您实际上是在询问是否

a[n] == a[i]

但是如果您的数组a是 size 数组n，则会导致未定义的行为。

于 2016-06-27T14:18:25.547 回答
0

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

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

于 2016-06-28T07:13:36.247 回答