#!/usr/bin/python2

# Find the Access Codes
# =====================

# In order to destroy Commander Lambda's LAMBCHOP doomsday device, you'll need
# access to it. But the only door leading to the LAMBCHOP chamber is secured
# with a unique lock system whose number of passcodes changes daily. Commander
# Lambda gets a report every day that includes the locks' access codes, but
# only she knows how to figure out which of several lists contains the access
# codes. You need to find a way to determine which list contains the access
# codes once you're ready to go in.

# Fortunately, now that you're Commander Lambda's personal assistant, she's
# confided to you that she made all the access codes "lucky triples" in order
# to help her better find them in the lists. A "lucky triple" is a tuple (x, y,
# z) where x divides y and y divides z, such as (1, 2, 4). With that
# information, you can figure out which list contains the number of access
# codes that matches the number of locks on the door when you're ready to go in
# (for example, if there's 5 passcodes, you'd need to find a list with 5 "lucky
# triple" access codes).

# Write a function solution(l) that takes a list of positive integers l and
# counts the number of "lucky triples" of (li, lj, lk) where the list indices
# meet the requirement i < j < k. The length of l is between 2 and 2000
# inclusive. The elements of l are between 1 and 999999 inclusive. The answer
# fits within a signed 32-bit integer. Some of the lists are purposely
# generated without any access codes to throw off spies, so if no triples are
# found, return 0.

# For example, [1, 2, 3, 4, 5, 6] has the triples: [1, 2, 4], [1, 2, 6], [1, 3,
# 6], making the answer 3 total.


# Test cases
# ==========
# Your code should pass the following test cases.
# Note that it may also be run against hidden test cases not shown here.

# Input:
# solution.solution([1, 2, 3, 4, 5, 6])
# Output:
#     3

# Input:
# solution.solution([1, 1, 1])
# Output:
#     1
    
## O(n^2)
def solution(l):
    c = [0] * len(l)
    count = 0
    for i in range(0, len(l)):
        for j in range(0, i):
            if l[i] % l[j] == 0:
                c[i] = c[i] + 1
                count = count + c[j]
    return count

## O(n^3)
def solution2(l):
    c = 0
    while len(l) > 2:
        t = l[1:]
        for id,i in enumerate(t):
            if i % l[0] == 0:
                for j in t[(id + 1):]:
                    if j % i == 0:
                        c += 1
        l = l[1:]
    return c

## Way too much memory, it's not even funny
## python is supposed to do list comprehension in a good way, lol
## adapted from https://oeis.org/A333885
def solution3(l):
    return len([(i, j, k)
                for id,i in enumerate(l)
                for jd,j in enumerate(l[(id+1):])
                for k in l[(id+jd+2):]
                if j%i==0 and k%j==0])

def solve(l):
    print(l)
    print(solution(l))

solve([1, 2, 3, 3, 5, 2])
solve([1, 2, 3, 4, 5, 6])
solve([1, 2, 3, 3, 2, 1])
solve([1 for x in xrange(2000)])
solve([1, 1, 1])
solve([])
solve([2])
solve([2, 5])
solve([1, 5, 6])
solve([1, 999999, 2])