高新区网站建设 意义,网站开发团队人数构成,哈尔滨市建设工程交易中心网站,建网站算法题意#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;
}