-1

ハッカーランクでこの問題を解決しようとしていました。

N、S、P、Q の 4 つの整数が与えられます。これらを使用して、次の疑似コードでシーケンスを作成します。

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

unsigned long longはい、 C++ では配列を使用できます。しかし、あなたが持っているのは配列ではありません:定数であるunsigned long long a[n];必要があります。n(これは C では異なりますが、C++ を作成しています)。

それがまだ実行されるのは、C と C++ を混在させることができるコンパイラ拡張機能ですが、動作は定義されていません。特にエラー処理が不足しているようです。

于 2016-06-28T07:13:36.247 に答える
0

この回答は、以前のバージョンのコードに対するものでした。コードは質問内で編集されました (j = i および i = n は 2 つのブレークに置き換えられました)。

ケースに遭遇したときに何が起こるかを見てください

a[i] == a[j]

に設定jしi、次にiに設定しますn。しかしiは よりも小さいnので、ステートメントj<iは真のままです。その後、 for ループが実行され続けるため、プログラムは評価を試みます

a[i] == a[j]

あなたが割り当てた新しい値で、あなたは実際に尋ねています

a[n] == a[i]

ただしa、配列が size の配列である場合n、これは未定義の動作につながります。

于 2016-06-27T14:18:25.547 に答える