张店网站建设公司,网络广告的计费方式,seo工具共享网站,彩票资料网站怎么做题意#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;
}
