Индийская легенда рассказывает историю о предполагаемом изобретателе шахматной игры, который настолько впечатлил императора Индии своей игрой, что он получит вознаграждение за все, что попросит.

Человек сказал, что хочет, чтобы ему заплатили рисом. Он хотел рисовое зерно для первого квадрата шахматной доски, два для второго, четыре для третьего, восемь для четвертого и так далее до 64-го квадрата.

Император был поражен, что этот человек попросил такую ​​маленькую награду, но когда его математики начали считать, он потерял одну из своих провинций.

задача

Учитывая длину стороны гипотетической шахматной доски (на шахматной доске по умолчанию 8) и множитель между квадратами (на легенде 2), подсчитайте количество рисовых зерен, которые император должен заплатить человеку.

Заметки

• Длина стороны всегда будет положительным целым числом. Вместо этого множитель может быть любым рациональным числом.

• Если выбранный вами язык не может отображать очень большие числа, это нормально, если ваша программа может правильно обрабатывать вводимые данные меньшего размера.

• Кроме того, если ваш язык выбора округляет большие значения (с экспоненциальными обозначениями), то все в порядке, если эти значения приблизительно верны.

Testcases

Input (side length, multiplier) => Output
8, 2                            => 18446744073709551615
3, 6                            => 2015539
7, 1.5                          => 850161998.2854
5, -3                           => 211822152361
256, 1                          => 65536
2, 2                            => 15
2, -2                           => -5

Обратите внимание, что явная формула

result = (multiplier ^ (side ^ 2) - 1) / (multiplier - 1)

Выполняет неправильно multiplier = 1, как

1 ^ (side ^ 2) - 1 = 0
1 - 1 = 0
0 / 0 != side ^ 2 (as it should be)

счет

Это код-гольф. Кратчайший ответ в байтах побеждает.

Желе , 4 байта

²b1ḅ

Это использует подход из умного APL-ответа @ APLDude .

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

Как это работает

²b1ḅ  Main link. Arguments: x (side length), y (multiplier)

²     Square; yield x².
 b1   Convert to base 1 (unary), yielding a list of x² ones.
   ḅ  Convert from base y to real number.
      This yields y^(x²-1) + ... + y + 1.

MATL , 6 байтов

2^:q^s

Попробуйте онлайн!

2^   % Take implicit input, say N, and square it: N^2
:q   % Generate array [0 1 ... N^2-1]
^    % Take implicit input, M, and compute [M^0 M^1 ... M^(N^2-1)]
s    % Sum of the array. Implicit display

APL, 10 байт

⎕⊥1+0×⍳⎕*2

⎕используется для чтения ввода пользователя дважды. Если мы сохраним длину стороны в s и множитель в m , мы получим следующий код.

m⊥1+0×⍳s*2

И вот как APL анализирует этот код:

Python, 40 байт

lambda n,m:eval('1+m*('*n*n+'0'+')'*n*n)

Создает и оценивает строку как

1+m*(1+m*(1+m*(1+m*(0))))

который кодирует сумму как Hornerized многочлен с n*nусловиями.

Множество разных методов дали очень похожие количества байтов:

#String evaluation
lambda n,m:eval('1+m*('*n*n+'0'+')'*n*n)   #40

#Direct summation
lambda n,m:sum(m**i for i in range(n*n))   #40
lambda n,m:sum(map(m.__pow__,range(n*n)))  #41

#Direct formula
lambda n,m:n*n*(1==m)or(m**n**2-1)/(m-1)   #40

#Iterative sequence
f=lambda n,m,j=0:j<n*n and 1+m*f(n,m,j+1)  #41
def f(n,m):s=0;exec"s=s*m+1;"*n*n;print s  #41

#Recursive expression
#Fails due to float imprecision of square root
f=lambda n,m:n and 1+m*f((n*n-1)**.5,m)    #39*

Pyth, 6 байт

1 байт сохранен благодаря @FryAmTheEggman .

s^Lvz*

Попробуйте онлайн!

Тестирование.

Haskell, 25 байт

n%m=sum$(m^)<$>[0..n*n-1]

Суммирует список [m^0, m^1, ..., m^(n*n-1)].

JavaScript (ES2016 / ES7), 31 29 28 байт

a=>b=>(b**(a*a)-1)/--b||a*a

Просто @Bassdrop Cumberwubwubwub и @ Kaizo версия ES6, но с оператором возведения в степень. :) (У меня не было достаточно репутации, чтобы комментировать вместо этого.)

Изменить: /+(b-1)изменилось на /--b(спасибо @Neil).

Редактировать: теперь использует карринг (спасибо @MamaFunRoll).

Желе, 6 байт

²R’*@S

Попробуйте онлайн!

MATLAB, 23 байта

@(n,k)sum(k.^(0:n^2-1))

Проверьте это здесь !

Javascript ES6, 59 37 35 34 байта

a=>b=>(Math.pow(b,a*a)-1)/--b||a*a` 

Спасибо @Kaizo за сокращение 19 байт, @Neil за еще 2 и @gcampbell еще за 1!

Попробуй здесь

f=
a=>b=>(Math.pow(b,a*a)-1)/--b||a*a

a.innerHTML='<pre>'+
  [[8,2],
   [3,6],
   [7,1.5],
   [5,-3],
   [256,1],
   [2,2],
   [2,-2]].map(b=>`${b[0]}, ${b[1]} => ${f(b[0])(b[1])}`).join('<br>')+'</pre>'

<div id=a>

Альтернативные битые версии

32 байта

(a,b)=>(Math.pow(b,a*a)-1)/(b-1)

Причины NaNдля b==1.

30 байт

(a,b)=>(Math.pow(b,a*a)-1)/~-b

Причины Infinityдля b==1.5.

28 байт

(a,b)=>~-Math.pow(b,a*a)/~-b

Выходы 1для некоторых действительных тестовых случаев.

Старая версия на 59 байт

(a,b)=>Array(a*a).fill``.reduce((c,d,i)=>c+Math.pow(b,i),0)

Java, 132 байта

import java.math.*;Object e(int n,BigDecimal m){BigDecimal r=BigDecimal.ONE,a=r;for(n*=n;n>1;n--)r=r.add(a=a.multiply(m));return r;}

Ungolfed

import java.math.*;

Object e(int n, BigDecimal m) {
    BigDecimal r = BigDecimal.ONE, a = r;
    for (n *= n; n > 1; n--)
        r = r.add(a = a.multiply(m));
    return r;
}

Заметки

• Это будет работать для произвольно больших выходных данных, как того требует OP (Жаль, что Java поддерживает большие числа, в противном случае это будет короче).

Выходы

Input:      8 2.0
Expected:   18446744073709551615
Actual:     18446744073709551615

Input:      3 6.0
Expected:   2015539
Actual:     2015539

Input:      7 1.5
Expected:   850161998.2854
Actual:     850161998.285399449204543742553141782991588115692138671875

Input:      5 -3.0
Expected:   211822152361
Actual:     211822152361

Input:      256 1.0
Expected:   65536
Actual:     65536

Input:      2 2.0
Expected:   15
Actual:     15

Input:      2 -2.0
Expected:   -5
Actual:     -5

Input:      263 359.9
Expected:   ?
Actual:     9709...[176798 digits]...7344.7184...[69160 digits]...6291

R, 18 байт

sum(m^(1:s^2-1))

Объяснение:

sum(               # Calculate sum
    m              # Multiplier
     ^             # Exponentiate
      (1:s^2-1))   # Generate sequence from 1 to s(ide)^2-1

05AB1E , 5 байтов

Код:

nL<mO

Объяснение:

n      # Compute i ** 2
 L     # Push the list [1, ..., i ** 2]
  <    # Decrement by 1, [0, ..., i ** 2 - 1]
   m   # Power function with implicit input, [0 ** j, ..., (i ** 2 - 1) ** j]
    O  # Sum that all up

Попробуйте онлайн! ,

Haskell, 30 байт

n#m=sum$take(n^2)$iterate(*m)1

или одинаково долго

n%1=n^2
n%m=(m**(n*n)-1)/(m-1)

Первая версия начинается с 1многократного умножения на m. Затем он суммирует первые n^2числа этой последовательности. Вторая версия - это явная формула, как видно из других ответов.

J, 10 байт

+/@:^i.@*:

использование

Я отмечаю некоторые целые числа xсуффиксом, чтобы использовать расширенные целые числа для получения точных результатов.

   f =: +/@:^i.@*:
   2x f 8
18446744073709551615
   3x f 6
75047317648499560
   6x f 3
2015539
   1.5 f 7
8.50162e8
   _3x f 5
211822152361
   1 f 256
65536
   2 f 2
15
   _2 f 2
_5

объяснение

+/@:^i.@*:
        *:  Square the value s to get s^2
     i.@    Make a range from 0 to s^2 exclusive, [0, 1, ..., s^2-1]
    ^       Using m as the base, calculate the power with the range
            [m^0, m^1, ..., m^(s^2-1)]
+/@:        Sum the entire list and return it

Mathcad, [tbd] байт (~ 11)

Использует встроенный в Mathcad оператор суммирования. Также демонстрирует упрощение символьного процессора для генерации точной формулы.

Mathcad эффективно запускает два обработчика параллельно - один с 64-разрядной стандартной плавающей запятой IEEE, а другой - символьный процесс произвольной длины (MuPad). Стандартная числовая оценка обозначается знаком равенства (=), в то время как стрелка вправо указывает на символическую оценку.

Схема подсчета Mathcad еще не определена, поэтому подсчет байтов не производится.

ctl- $ вводит оператор суммирования (Sigma), включая пустые заполнители, чтобы поместить переменную суммирования, начальное значение, конечное значение и выражение. Приблизительное число эквивалентных байтов = 11.

PostgreSQL, 67 66 байт

SELECT SUM(m^v)FROM(VALUES(3,6))t(s,m),generate_series(0,s*s-1)s(v)

SqlFiddleDemo

Входные данные: VALUES(side, multiplier)

РЕДАКТИРОВАТЬ:

Ввод перенесен в таблицу, все случаи одновременно:

SELECT s,m,SUM(m^v)FROM i,generate_series(0,s*s-1)s(v)GROUP BY s,m

SqlFiddleDemo

Выход:

╔══════╦══════╦══════════════════════╗
║  s   ║  m   ║         sum          ║
╠══════╬══════╬══════════════════════╣
║   7  ║ 1.5  ║ 850161998.2853994    ║
║   2  ║ 2    ║ 15                   ║
║   2  ║ -2   ║ -5                   ║
║ 256  ║ 1    ║ 65536                ║
║   5  ║ -3   ║ 211822152361         ║
║   8  ║ 2    ║ 18446744073709552000 ║
║   3  ║ 6    ║ 2015539              ║
╚══════╩══════╩══════════════════════╝

TI-Basic, 19 байтов

Sэто длина стороны, и Mэто множитель.

Prompt S,M:Σ(M^I,I,0,S²-1

Python, 40 байт

lambda l,m:sum(m**i for i in range(l*l))

Рубин: 39 байт

->s,m{(0...s*s).reduce(0){|a,b|a+m**b}}

Тест:

f = ->s,m{(0...s*s).reduce(0){|a,b|a+m**b}}

f[8,2]   # 18446744073709551615
f[3,6]   # 2015539
f[7,1.5] # 850161998.2853994
f[5,-3]  # 211822152361
f[256,1] # 65536
f[2,2]   # 15
f[2,-2]  # -5
f[1,1]   # 1

Python, 41 байт

Абсолютно новый в этой игре в гольф, критика приветствуется!

lambda n,m:sum(m**i for i in range(n**2))

Джольф, 18 15 10 байт

Спасибо Cᴏɴᴏʀ O'Bʀɪᴇɴ за сохранение 3 байта и указание мне на отображение

uΜzQjd^JwH

Попробуй это здесь!

 ΜzQj       Map over an array of 1 -> square(side length)
     d^JwH  Set the current array value to multiplier^(current value - 1)
u           Sum the array

CJam , 9 байт

q~2#,f#:+

Входные данные в обратном порядке разделяются новой строкой или пробелом.

Попробуйте онлайн!

q~    e# Read input. Evaluate: pushes the two numbers, M and N, onto the stack
2#    e# Square: compute N^2
,     e# Range: generates array [0 1 ... N^2-1]
f#    e# Compute M raised to each element of the array [0 1 ... N^2-1]
:+    e# Fold addition: compute sum of the array [M^0 M^1 ... M^(N^2-1)]

PHP, 58 54 байта

<?function a($n,$m){$n*=$n;echo(1-$m**$n)/(1-$m)?:$n;}

Это просто использует формулу суммирования, чтобы показать значение, после проверки, равен ли множитель 1 (что возвращает NAN в формуле).

Mathematica, 22 байта

Tr[#^(Range[#2^2]-1)]&

Создает диапазон {1, 2, ... s^2}, вычитает 1 над ним, чтобы сделать {0, 1, ..., s^2-1}. Затем возведите каждого в силу mсоздания {m^0, m^1, ..., m^(s^2-1)}и верните сумму.

В качестве альтернативы, Mathematica может использовать явную формулу, взяв ее предел. Это требует 29 байтов.

Limit[(s^#^2-1)/(s-1),s->#2]&

PARI / GP , 25 байтов

f(s,m)=sum(i=0,s^2-1,m^s)

Дольше, но быстрее (35 байт):

f(s,m)=if(m==1,s^2,(m^s^2-1)/(m-1))

Милый (30 байт):

f(s,m)=vecsum(powers(m,s^2-1))

C #, 56 байт

double f(int n,double q){return(Math.Pow(q,n*n)-1)/--q;}

Луа, 54 47 байт

r=0l,m=...for i=0,l^2-1 do r=r+m^i end print(r)

Запустите из командной строки с длиной стороны доски в качестве первого аргумента и множителя в качестве второго.

Спасибо user6245072 за сохранение 6 байтов и Katenkyo за сохранение дополнительных 1.

Оригинальная 54-байтовая версия:

a,b=...c=1 d=1 for i=2,a^2 do c=c*b d=d+c end print(d)

𝔼𝕊𝕄𝕚𝕟, 11 символов / 14 байтов

⨭⩥ î²)ⓜⁿ⁽í$

Try it here (Firefox/WebKit Nightly only).

Да, теперь работает в WebKit Nightly! Поддержка Chrome следующая.

объяснение

⨭⩥ î²)ⓜⁿ⁽í$ // implicit: î = input1, í = input2
   ⩥ î²)       // generate a range [0..î^2)
                     ⓜ      // map over range ($ is mapitem):
        ⁿ⁽í$  //   í^$
⨭            // sum resulting range
              // implicit output

ВОЗВРАТ , 32 байта

[a:2^0\
{[$¥][a;\^]#[¤¥][+]#]!

Try it here.

Анонимная лямбда, которая оставляет результат на Stack2. Использование:

8 2[a:2^0\
{[$¥][a;\^]#[¤¥][+]#]!

объяснение

[                              ]!  lambda
 a:                                store multiplier to a
   2^                              square side-length
     0\␊                           create range [0..result)
        {                          set current stack to range
         [  ][     ]#              while loop
          $¥                         check if TOS is truthy
              a;\^␌                  if so, push a^TOS to Stack2
                     ␁            set current stack to Stack2
                       [¤¥][+]#    sum Stack2