@[ztr2022](/user/713387) 最坏时间复杂度为 $\mathcal{O}(nm)$，$a_i$ 来个 $1$ 就寄了。还需要优化。
by NightStriker @ 2022-12-24 10:32:08
@[_ljp_](/user/714084) 但是这个已经优化到极致了吧……
by ztr_qwq @ 2022-12-24 10:36:51
我再想想
by ztr_qwq @ 2022-12-24 10:37:21
@[ztr2022](/user/713387)
没看题，但是[这](https://www.luogu.com.cn/blog/soul-spirit/solution-p2926)篇题解似乎能好一点？
by NightStriker @ 2022-12-24 10:38:10
@[_ljp_](/user/714084) 想出来了，已优化至O(nlogn)并AC，thx，此贴完结
by ztr_qwq @ 2022-12-24 10:46:36
@[ztr_qwq](/user/713387) 求助，我写了自认为是O(nlogn)的解法，但是还是测试点2和3超时，楼主或许可以分享一下修改之后的代码吗？我的86分代码如下
```c++
#include <iostream>
#include<vector>
using namespace std;
int main() {
vector<int>count(1000001, 0); //记录每个数出现的约数个数
int N;cin >> N;
vector<int>nums(N);
int maxNum = 0;
vector<int>cnt(N, 0);
for (int i = 0; i < N; i++) {
cin >> nums[i];
cnt[i]++;
maxNum = max(nums[i], maxNum);
}
for (int i = 0; i < N; i++) {
for (int j = nums[i]; j <= maxNum ; j += nums[i]) {
count[j]+=cnt[i];
}
}
for (int i = 0; i < N; i++) {
cout << count[nums[i]]-1 << endl;
}
}
by 耿耿要逆袭 @ 2023-03-25 16:30:51
@[耿耿要逆袭](/user/446823) 你这个和我一样，来个1就寄了
或许可以利用一个类似于哈希的思想？
而且不想你这样这么麻烦捏……
改正后代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+1;
int a[N/10],cnt[N],ans[N];
int main() {
int n,m=0;
scanf("%d",&n);
for (int i=1;i<=n;i++) {
scanf("%d",&a[i]);
cnt[a[i]]++;
}
for(int i=1;i<=N;i++)
for(int j=i;j<=N;j+=i)
ans[j]+=cnt[i];
for(int i=1;i<=n;i++)
printf("%d\n",ans[a[i]]-1);
return 0;
}
```
by ztr_qwq @ 2023-03-26 07:10:57
@[耿耿要逆袭](/user/446823) 当然最主要的还是筛选捏
by ztr_qwq @ 2023-03-26 07:13:14
@[耿耿要逆袭](/user/446823) 你珂以看看这个代码，对比一下有什么不同，如果不懂的话就去题解区学习一下叭qwq
by ztr_qwq @ 2023-03-26 07:16:47
@[ztr_qwq](/user/713387) 非常感谢，知道自己问题出在哪了！昨天没细看，代码压根就没优化qwq
by 耿耿要逆袭 @ 2023-03-26 10:51:04