本文最后更新于 2024年9月7日 下午
洛谷题目传送门 | SP 原题传送门
本题双倍经验,同主题库P2926
思路
又是一道桶的题。
首先暴力,对于 N=100000,复杂度 O(n2),显然超时。
考虑优化。
看题面,不难想到用桶记录每个数字的出现次数,只需要遍历数组找到比 ai 小的数即可。
但是这样仍然超时,继续优化。发现遍历数组时没必要全遍历一边,只需要遍历到 n 即可。
注意以下几点:
-
对于完全平方数,n 会计算两遍,此时答案数减一;
-
奶牛会拍到自己的头,答案数还需要减一。
然后就可以看见一篇绿色了。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| #include<cmath> #include<iostream> #include<algorithm> using namespace std; inline int read() { int s=0,w=1; char ch=getchar(); while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar(); return s*w; } const int N=1e5+10; int n,ans=0; int a[N],t[1000010]; int main() { n=read(); for(int i=1;i<=n;i++) { a[i]=read(); t[a[i]]++; } for(int i=1;i<=n;i++) { ans=0; for(int j=1;j<=sqrt(a[i]);j++) { if(a[i]%j==0) { ans+=t[j]+t[a[i]/j]; if(j*j==a[i]) { ans-=t[j]; } } } cout<<ans-1<<endl; } return 0; }
|