Найти Простой Суммы


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


Вы только учитесь код и закончите с петель и функции. Теперь, вам дают следующий псевдокод:

/*
 * The function has two integer parameters: k and n
 * The function returns the value of sum
 */
    function f(k, n) {
    sum = 0;

    for (i = 1; i ≤ n; i += 1) {
        sum += i;
        i *= k;
    }

    return sum;
}

За три даны целые числа k,a и B, найти значения s мод (10^9 + 7), где S определяется как:

$с $=\sum_{N=а}^б▒〖ф(к,N)$$

Формат Входного Сигнала

В первой строке входных данных находится целое число Q, то общее количество запросы. Каждая из следующих Q строк содержит три разделенных пробелом чисел K,A и B

Формат

Для каждого запроса выведите значение S мод (10^9 + 7) на новой строке.

Образец Ввода

4
2 1 5
3 1 5
4 1 5
5 1 5

Пример Вывода

14
13
10
5

Объяснение

Query 2 1 5
f(2,1) = 1
f(2,2) = 1
f(2,3) = 4
f(2,4) = 4
f(2,5) = 4

Таким образом, с = ф(2,1)+Ф(2,2)+Ф(2,3)+Ф(2,4)+Ф(2,5) = 14

 Query 3 1 5

 f(3,1) = 1
 f(3,2) = 1
 f(3,3) = 1
 f(3,4) = 5
 f(3,5) = 5

Таким образом, с = ф(3,1)+Ф(3,2)+Ф(3,3)+Ф(3,4)+Ф(3,5) = 13

 Query 4 1 5
 f(4,1) = 1
 f(4,2) = 1
 f(4,3) = 1
 f(4,4) = 1
 f(4,5) = 6

Таким образом, с = ф(4,1)+Ф(4,2)+Ф(4,3)+Ф(4,4)+Ф(4,5) = 10

 Query 5 1 5
 f(5,1) = 1
 f(5,2) = 1
 f(5,3) = 1
 f(5,4) = 1
 f(5,5) = 1

Таким образом, с = ф(5,1)+Ф(5,2)+Ф(5,3)+Ф(5,4)+Ф(5,5) = 5


import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class maxSum {

static int simplestSum(int k, int a, int b) {
    int count = 1;
    int totalSum = 0;
    while(count <= b) {
        int z = maxSum(k, a);
        int mul = k*a;
        if(mul < b) {
            totalSum = totalSum + (z*(k*a));
        }else {
            totalSum = totalSum + (z*((b-count)+1));
        }

        count = count + (k*a);
        a = count;
    }
    return totalSum;
}

static int maxSum(int k , int a) {
    int sum = 0;
     for (int i = 1; i <= a; i += 1) {
         sum += i;
         i *= k;
     }
     return sum;
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int q = in.nextInt();
    for(int a0 = 0; a0 < q; a0++){
        int k = in.nextInt();
        int a = in.nextInt();
        int b = in.nextInt();
        int result = simplestSum(k, a, b);
        System.out.println(result);
    }
    in.close();
   }
}


356
1
задан 27 января 2018 в 08:01 Источник Поделиться
Комментарии
1 ответ

     function f(k, n) {
summ = 0
max = n*k;
for (i = 0; i < max; i += k)
summ += i

return sum;
}

или еще проще, используя формулы сумм:

summ = k + 2k + ... + nk = (k + nk) + (2k + (n-1)k) +... =  k*(n+1)*n/2

function f(k, n) {
return (n+1)*n/2 *k;
}

2
ответ дан 28 января 2018 в 12:01 Источник Поделиться