Сохранение неизвестного количества целых чисел без лишнего времени/памяти

Question

#include <iostream> 

using namespace std; 

unsigned long long divsum(unsigned long long x); 

int main() 
{ 
    unsigned long long x; 
    cin >> x; 
    unsigned long long y[200000]; 
    for (unsigned int i = 0; i < x; i++) 
     cin >> y[i]; 
    for (unsigned int i = 0; i < x; i++){ 
     cout << divsum(y[i]) << endl; 
    } 
    return 0; 
} 

unsigned long long divsum(unsigned long long x){ 
    int sum = 0; 
    for(unsigned int i = 1; i <= x/2; i++){ 
     if(x % i == 0) 
      sum += i; 
    } 
    return sum; 
} 

Я делаю онлайн-упражнение, и в нем говорится, что в первой строке есть 2000000 дел, поэтому я сделал массив этой суммы, однако, когда Я отправляю решение, это превышает время. Поэтому мне было интересно, что это альтернативный и быстрый способ сделать это? Программа работает отлично сейчас, за исключением того, что она превышает срок действия веб-сайта.

Answer 1

Поскольку вы знаете размер массива, попробуйте vector и reserve.

int main() 
    { 
     unsigned long long x; 
     cin >> x; 
     unsigned long long var; 
     vector<unsigned long long> y; 
     y.reserve(x); 
     for (unsigned int i = 0; i < x; i++){ 
      cin >> y[i]; 
     }for (unsigned int i = 0; i < x; i++){ 
      cout << divsum(var) << endl; 
     } 
     return 0; 
    } 

И дело в const &

const unsigned long long & divsum(const unsigned long long & x){ 
    int sum = 0; 
    unsigned long long x2 = x/2 
    for(unsigned int i = 1; i <= x2; i++){ 
     if(x % i == 0) 
      sum += i; 
    } 
    return sum; 
} 

Answer 2

Вы можете выделить массив динамически, поэтому он будет работать лучше в тех случаях, когда x < 200000

int main() 
{ 
    unsigned long long x; 
    cin >> x; 
    unsigned long long *y = new unsigned long long[x]; 
    // you can check if new didn't throw an exception here 
    for (unsigned int i = 0; i < x; i++) 
     cin >> y[i]; 
    for (unsigned int i = 0; i < x; i++){ 
     cout << divsum(y[i]) << endl; 
    } 
    delete[] y; 
    return 0; 
}