local mfl, mce = math.floor, math.ceil local mmi, mma = math.min, math.max local bls, brs = bit.lshift, bit.rshift local ffi = require("ffi") local C = ffi.C local function getgcd(x, y) while 0LL < x do x, y = y % x, x end return y end local SegTree = {} SegTree.updateAll = function(self) for i = self.stagenum - 1, 1, -1 do local cnt = bls(1, i - 1) for j = 1, cnt do self.stage[i][j] = self.func(self.stage[i + 1][j * 2 - 1], self.stage[i + 1][j * 2]) end end end SegTree.create = function(self, n, func, emptyvalue) self.func, self.emptyvalue = func, emptyvalue local stagenum, mul = 1, 1 self.stage = {} self.stage[1] = ffi.new("int64_t[?]", 2) while mul < n do mul, stagenum = mul * 2, stagenum + 1 self.stage[stagenum] = ffi.new("int64_t[?]", mul + 1) end self.stagenum = stagenum -- for i = 1, mul do self.stage[stagenum][i] = emptyvalue end self.spos = {} for i = 1, n do local sp, sz = 1, bls(1, stagenum - 1) while(i - 1) % sz ~= 0 do sp = sp + 1 sz = brs(sz, 1) end self.spos[i] = sp end end SegTree.setSilent = function(self, idx, value) self.stage[self.stagenum][idx] = value end SegTree.right_bound = function(self, left, right) local ret, retpos = self.emptyvalue, left - 1 local stage, l, r = self.spos[left], left, right local stagenum = self.stagenum while true do local sz = bls(1, stagenum - stage) -- while (l - 1) % sz ~= 0 or r + 1 - l < sz do while r + 1 - l < sz do stage = stage + 1 sz = bls(1, stagenum - stage) end local tmp = self.func(ret, self.stage[stage][mce(l / sz)]) if 1LL < tmp then ret, retpos = tmp, l + sz - 1 if retpos == right then break end if l + sz <= r then stage, l, r = self.spos[l + sz], l + sz, r else break end else if sz ~= 1 then stage, l, r = stage + 1, l, l + sz - 2 else break end end end return retpos + 1 end SegTree.new = function(n, func, emptyvalue) local obj = {} setmetatable(obj, {__index = SegTree}) obj:create(n, func, emptyvalue) return obj end local n = io.read("*n", "*l") local st = SegTree.new(n, getgcd, 0LL) ffi.cdef[[ long long atoll(const char*); ]] local s = io.read() do local i = 1 for w in s:gmatch("%d+") do st.stage[st.stagenum][i] = C.atoll(w) i = i + 1 end end -- print(os.clock()) st:updateAll() -- print(os.clock()) local ret = 0 local z = n for i = n, 1, -1 do local p = st:right_bound(i, z) ret = ret + n + 1 - p z = mmi(p, n) end print(ret) -- print(os.clock())