这题的求解,首先要根据数据规模和时间要求,设计符合的算法。

  1. 求1到n的全部数的约束个数和,自然的思考方式,是看每个数的约束个数然后相加,这种计算复杂度O(n2)O(n^2)

  2. 思考:因为1到n任一数的约数范围是1到那个数,那么我们可以遍历1到n,看每个数在1到n中有多少个倍数,也就是看1到n多少个数以其为约数,复杂度O(n)O(n)