pair_sum_floor.py

class fenwick_tree():
    n=1
    data=[0 for i in range(n)]
    def __init__(self,N):
        self.n=N
        self.data=[0 for i in range(N)]
    def add(self,p,x):
        assert 0<=p<self.n,"0<=p<n,p={0},n={1}".format(p,self.n)
        p+=1
        while(p<=self.n):
            self.data[p-1]+=x
            p+=p& -p
    def sum(self,l,r):
        assert (0<=l and l<=r and r<=self.n),"0<=l<=r<=n,l={0},r={1},n={2}".format(l,r,self.n)
        return self.sum0(r)-self.sum0(l)
    def sum0(self,r):
        s=0
        while(r>0):
            s+=self.data[r-1]
            r-=r&-r
        return s

import random
N=1000
maxA=1000
A=[random.randrange(1,maxA+1) for i in range(N)]
#x^2<=Kとなる最大のxを返す
def sqrt(K):
    low=0
    high=K+10
    while(high-low>1):
        mid=(high+low)//2
        if mid*mid<=K:
            low=mid
        else:
            high=mid
    return low
#O(Nsqrt(maxA))
def solve_1(A):
    N=len(A)
    maxA=max(A)
    sqrtmaxA=sqrt(maxA)
    L=[0 for i in range(sqrtmaxA)]
    BIT=fenwick_tree(maxA+1)
    ans=0
    for i in range(N):
        if A[i]<sqrtmaxA:
            ans+=L[A[i]]
        else:
            for k in range(0,maxA+1,A[i]):
                ans+=(k//A[i])*BIT.sum(k,min(k+A[i],maxA+1))
        BIT.add(A[i],1)
        for j in range(1,sqrtmaxA):
            L[j]+=A[i]//j
    return ans
#愚直解(O(N^2))
def solve_2(A):
    N=len(A)
    ans=0
    for i in range(N):
        for j in range(i+1,N):
            ans+=A[i]//A[j]
    return ans
#print(A)
ans1=solve_1(A)
ans2=solve_2(A)
print(ans1,ans2)