有这样一段程序，fun会对整数数组A进行求值，其中Floor表示向下取整：

 

fun(A)

    sum = 0

    for i = 1 to A.length

        for j = i+1 to A.length

            sum = sum + Floor((A[i]+A[j])/(A[i]*A[j])) 

    return sum

 

给出数组A，由你来计算fun(A)的结果。例如：A = {1, 4, 1}，fun(A) = [5/4] + [2/1] + [5/4] = 1 + 2 + 1 = 4。

Input

第1行：1个数N，表示数组A的长度(1 <= N <= 100000)。

第2 - N + 1行：每行1个数A[i]（1 <= A[i] <= 10^9)。

Output

输出fun(A)的计算结果。

Input示例

3

1 4 1

Output示例

4

按照定义做会超时，也不会那么简单的 ，需要找一定的规律
(1+1)/1 = 2     1 < (1+n)/n < 2  n > 1  取整后为1
(2+2)/4 = 1
事实上 (a + b)/ab = 1/a + 1/b  a>2且b>2时 不等式(a+b)/ab < 1  a,b不全为2时等号成立
取整后为0 ， 所以只用查找1和2，以及>=2的个数即可
公式：sum = 2(N1-1)*N1/2 + N1*(∑Nk  k>=2) + N2*(N2-1)/2
注意乘的次数

#include <stdio.h>

#define LL long long

int N, n;

int one, two, other;

int main()

{

    //freopen("1.txt", "r", stdin);

    scanf("%d", &N);

    for (int i = ; i < N; i++) {

        scanf("%d", &n);

        if (n == )

            one++;

        if (n == )

            two++;

        if (n >= )

            other++;

    }

    LL sum = ;

    sum += (one-)*one + one*other + ( (two*(two-))>> );

    printf("%lld\n", sum);

    return ;

}