СГМ из divizors чисел меньше или равно N

Question

мне действительно нужна помощь в этой проблеме:

Учитывая положительное целое N мы определяем xsum(N) как сумма СГМ чисел всех положительных целого числа делителей меньше или равна N.

Например: xsum (6) = 1 + (1 + 2) + (1 + 3) + (1 + 2 + 4) + (1 + 5) + (1 + 2 + 3 + 6) = 33.
(xsum - сумма divizors 1 + сумма divizors от 2 + ... + сумма DIV 6)

Учитывая положительное целое число K, вы просили, чтобы найти самые низкие N что удовлетворяет Состояние: xsum(N) >= K

К ненулевой натуральное число, которое имеет не более 14 цифр

ограничение по времени: 0,2 сек

Очевидно, что грубая сила будет выпадать для большинства случаев с превышением лимита времени. Я еще не нашел что-то получше, так что это код:

fscanf(fi,"%lld",&k); 
i=2; 
sum=1; 
while(sum<k) { 
    sum=sum+i+1; 
    d=2; 
    while(d*d<=i) { 
      if(i%d==0 && d*d!=i) 
      sum=sum+d+i/d; 
      else 
      if(d*d==i) 
       sum+=d; 
      d++; 
    } 
    i++; 
} 

Любые лучшие идеи?

Answer 1

Для каждого номера n в диапазоне [1, N] применяется следующее: n - это делитель точно цифр roundDown(N/n) в диапазоне [1, N]. Таким образом, для каждого n мы добавим итог n * roundDown(N/n) к результату.

int xsum(int N){ 
    int result = 0; 

    for(int i = 1 ; i <= N ; i++) 
     result += (N/i) * i;//due to the int-division the two i don't cancel out 

    return result; 
} 

Идея этого алгоритма как хорошо может быть использован для решения основной задачи-(smallest N such that xsum(N) >= K) в более быстрое время, чем полный перебор.

Полный поиск может быть дополнительно оптимизирована с использованием некоторых правил, мы можем извлечь из приведенного выше кода: K = minN * minN (minN будет правильный результат, если K = 2 * 3 * ...) Используя эту информацию, мы имеем низший переплете для начала поиска

..

Следующий шаг должен был бы искать для верхней границы. Поскольку рост xsum(N) является (приблизительно) квадратичная мы можем использовать это, чтобы приблизить N. Эта оптимизированная угадывание позволяет найти искомую стоимость довольно быстро.

int N(int K){ 
    //start with the minimum-bound of N 
    int upperN = (int) sqrt(K); 
    int lowerN = upperN; 

    int tmpSum; 
    //search until xsum(upperN) reaches K 
    while((tmpSum = xsum(upperN)) < K){ 
     int r = K - tmpSum; 

     lowerN = upperN; 
     upperN += (int) sqrt(r/3) + 1; 
    } 

    //Now the we have an upper and a lower bound for searching N 
    //the rest of the search can be done using binary-search (i won't 
    //implement it here) 

    int N;//search for the value 

    return N; 
}