求救救救救救

问题讨论区 普及段
21

不是泥。。。

22

怎么样了？？？
@2345安全卫士 我的是老师的思路，用因数来构造数

23

此帖终，jym解决方案

24
25

错误原因：

1.第一版代码时间复杂度太长，最大达到 O(N*max(x_1,x_2...x_n)) 肯定过不了

2.第二版求每个数的因数采用的时间复杂度是 O(x_i/2) 过不了一点

正确方法：

将第二版代码的求每个数的因数改为 O(\sqrt{n}) 即可通过：

void f(int x){
  //cnt[x]++;
  for(int i=1;i<=sqrt(x);i++){
    if(x%i==0){
      cnt[i]++;
      if(x/i!=i){
        cnt[x/i]++;
      }
    }
  }
  return;
}
26

更正一下是 O(\displaystyle\sum_{i=1}^{n} \sqrt{a_i})

27

求每个数因数是 O(\sqrt{n}) 的，只是总代码的时间复杂度不同