蚂蚁笔试0309第三题

#牛客AI配图神器##牛客创作赏金赛##牛客创作赏金赛##ai智能作图#

```java

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        /**
        只要大的除小的就可以了
         */
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int[]a = new int[n];
        for (int i = 0; i < n; i++)a[i] = in.nextInt();

        Arrays.sort(a);
        long s = 0;
        for (int i = 0; i < n; i++) { //枚举起点
            int p = 1;
            int st = a[i];
            int l = i - 1, r = 0;
            while (st * p <= a[n - 1]) {   //寻找i的每个倍数的最近处
                int tar = st * p;
                r = find(a, tar);  //二分查找 p倍的最小处
                 s += (r - l) * (p - 1);
                l = r;
                p++;
            }
            s += (n  - l) * (p-1);//末尾计算
        }

        System.out.println(s);
    }

    public static int find(int[]a, int t) { //找到大于等于t的最小位置

        int l = 0, r = a.length - 1;
        while (l < r) {

            int mid = (l + r) >> 1;

            if (a[mid] < t)l = mid + 1;
            else r = mid;
        }
        return r;
    }
}```