测试数据弱了点啊

先暴力了一下，从0到n-1扫i，再从0到n-1扫j，判断累计一下进行输出，竟然过了，这数据有点弱了呀。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int a[N]; 
int main() {
	int n;
	cin>>n;
	for(int i=0; i<n; i++) cin>>a[i];
	for(int i=0; i<n; i++){
		int cnt=0;
		for(int j=1; j<n; j++){
			if(a[i]%a[(i+j)%n]==0) cnt++;
		}
		cout<<cnt<<endl;
	}
	return 0;
}

1≤N≤100,000，N^2的思路应该会超时才对。
实际上，在输入数据的同时可以统计每个数出现的次数，然后从1到最大值开始刷，如果这个数存在，将这个数的所有倍数的出现次数累加到这个数的答案上即可，最后输出要减1去掉本身。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int a[N],maxx;
int cnt[N*10]; //cnt[i] 记录数字i出现的次数 
int ans[N*10]; //记录数字i的答案
int main() {
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		scanf("%d", &a[i]);	
		cnt[a[i]]++;
		maxx=max(maxx, a[i]);
	} 
	for(int i=1; i<=maxx; i++){
		if(!cnt[i]) continue;
		for(int j=i; j<=maxx; j+=i) ans[j]+=cnt[i]; 
	}
	for(int i=0; i<n; i++) printf("%d\n",ans[a[i]]-1);
	return 0;
}