Hi Egor,
you may possibly stay within the tmieout with this algorithm:
(this isonly a test snippet, it uses fixed a and m)
local p={ 2,3,5,7,11,13,17,19 }
local m=2
local a=4
-- vektor of exponents
local i={}
local sum=0
-- k is the exponent to count through
-- u is the available occurrences
--
local function find( k, u )
if k==0 then
-- made a full counting step
-- compute the divisor from the prime factors
local f=1
for j,e in ipairs( i ) do
f = f * p[j] ^ e
end
-- multiply by frequency and add
sum = sum + f*u
while sum > 1000000007 do sum = sum - 1000000007 end
else
i[k-1] = 0
for x=0,a+k do
i[k] = x
find( k-1, u * (a+k+1-x) )
end
end
end
find(m, 1)
print(sum)
Am 04.01.2017 um 13:10 schrieb Egor Skriptunoff:
Hi!
I have made an attempt to use Lua as language for solving problems
in a programming contest.
I came across a situation where I can solve a problem using Pascal,
but not using Lua (4 test cases of 10 were failed due to timeout).
This is the problem I'm talking about:
https://www.hackerrank.com/contests/infinitum17/challenges/divisor-exploration-2
The contest is over, so it is OK to discuss the solutions.
