нахождение суммы цифр в артефактной последовательности

-4

У меня очень простой вопрос. Мне будет предоставлен первый термин арифметической прогрессии и общая разница. Мне нужно дать сумму цифр всех чисел между диапазоном L и R. Здесь сумма означает сумму < 10, что означает, что для числа говорят 157, сумма цифр равна 1 + 5 + 7 = 13, что равно далее 1 + 3 = 4. Диапазон - это индекс элементов. L означает L-номер этого ряда, а L начинается с 1. Здесь L и R могут быть от 1 до 10 18. Как я могу найти сумму этих цифр для такого большого диапазона. Я знаю, что цифра суммы числа n может быть рассчитана как (n-1)% 9 + 1. Но я не могу перебирать 10^18 номеров.нахождение суммы цифр в артефактной последовательности

Пример: предположим, что первый член арифметической прогрессии равен 14 и общая разница 7. Тогда сумма цифр всех чисел между 2 и 4 будет равна сумме (2 + 1) = 3 и (2 + 8) = (1 + 0) = 1 и (3 + 5) = 8, который равен 12

для картины нахождение

current=first; 
    ll arr[10]={0}; 
    while(1)// search for the pattern 
    { 
     ll dsum=(current-1)%9+1;// calculating digit sum 
     if(arr[dsum]!=0) 
     break; 
     arr[dsum]=ptr;// saving the value in the array by using hashing 
     ptr++; 
     current+=c_diff; 
    } 
for sum 

    for(ll i=1;i<ptr;i++) 
    { 
     sum[i]=sum[i-1]+new_arr[i]; 
    }

источник

2015-11-09 ankit kumar

См [Как задать хороший вопрос?] (Http://stackoverflow.com/help/how-to-ask) –

Добро пожаловать в StackOverflow! Сначала вам нужно попробовать что-то, и вы можете показать другим, что вы сделали, и какова конкретная проблема, с которой вы сталкиваетесь. –

Подсказка: повторяется ли эта последовательность (S (14, 7, 2) = {3, 1, 8, ...})? Докажите это. Вы будете хорошо на пути к большому упрощению проблемы. – Beta

Поскольку все номера будут (в конечном счете) сводится к одной цифре, вы должны иметь повторение после определенного количества терминов и, что максимум 9. (потому что 10 цифр, но 0 невозможно повторить).

Итак, давайте начнем с примера. Скажем, a=14, d=7, l=2, r=50. Я изменил значение r из вашего примера.

Так, пытаясь найти повторение:

Наш массив повторения q (скажем). Затем 1-й член q равен 5 (с 14 = 5).
Теперь следующий термин равен 21 (= 3). Поскольку 3 не равно 5, мы продолжаем.
Мы находим все условия, пока не получим 5. Так, q будет выглядеть следующим образом в этом примере:
```
q[] = {5,3,1,8,6,4,2,9,7} ... and then we have 5 again, so stop. 
```

Таким образом, наш повторяющийся рисунок имеет 9 членов. Теперь найти кумулятивный массив сумму с этим, который будет как:

sum[] = {5,8,9,17,23,27,29,38,45}

Теперь, так как r=50, найти сумму r терминов, который будет:

(floor)(50/9) * 45 + sum[50%9] 
= 5 * 45 + 23 
= 248

Теперь, так же, найти сумму . из l-1 терминов, (так как вы должны найти сумму в диапазоне l..r включительно

сумма 1 (2-1) = 1 условия будут:

(floor)(1/9) * 45 + sum[1 % 9] 
= 0 + 5 
= 5

Итак, ответ, 248 - 5 = 243.

источник

2015-11-09 05:03:50 vish4071

максимум 9 терминов могут повторяться не 10 –

Конечно, '0' будет там. – vish4071

Я реализовал тот же подход, но я получаю WA для некоторых случаев, когда L и R могут иметь диапазон 10^18. –

хорошо вы можете решить эту проблему, взяв два массива элементов 9 и найти термин LtH элемент.
с 1-го семестра найти цифру суммы l-го элемента и сохранить ее в двух массивах соответственно.

w1 = а + (л-1) * д
для (I = 1, J = w1; я < = 9; J + = д, я ++) {
, если (J% 9 == 0) {
array1 [i] = 9;
array2 [i] = 9;
}
else {
array1 [i] = j% 9;
массив2 [I] = J% 9;} }
Теперь д = г-л + 1
ш = ц/9 и е = д% 9
массив1 [I] = массив1 [я] * ж// in loop from i = 1 to 9
в array2 [i] = 0 // новый цикл от i = e + 1 до 9
теперь digitsum + = array1 [i] + array2 [i] // из цикла aa i = от 1 до 9, а цифра - это сумма всей цифры последовательности

эта цифра сумма решение.

источник

2015-11-12 20:46:02

нахождение суммы цифр в артефактной последовательности

ответ

Смежные вопросы