网站实施方案,大连在哪个网站做网上核名,怎么打开域名网站,注册公司网站怎么做题意#xff1a;求ai在n个数中#xff0c;ai可以整除的数有多少个#xff0c;不包括ai自己。
分析#xff1a;暴力写需要n^2的时间复杂度#xff0c;此时想一下预处理每个数的倍数#xff0c;约数和倍数是有关系的#xff0c;把每个数的倍数都加上1.
#includebits… 题意求ai在n个数中ai可以整除的数有多少个不包括ai自己。
分析暴力写需要n^2的时间复杂度此时想一下预处理每个数的倍数约数和倍数是有关系的把每个数的倍数都加上1.
#includebits/stdc.husing namespace std;const int N 1e6 10;
int s[N];
int cnt[N];
int a[N];int main()
{int n;cinn;for(int i1;in;i) {cina[i];cnt[a[i]];}for(int i1;iN;i)//这两重循环是O(nlogn)的{for(int ji;jN;ji){s[j]cnt[i];}}for(int i1;in;i) couts[a[i]]-1endl;return 0;
}
