洛谷题目传送门 | SP 原题传送门
本题双倍经验，同主题库P2926
思路
又是一道桶的题。
首先暴力，对于 N=100000N=100000，复杂度 O(n2)O(n^2)，显然超时。
考虑优化。
看题面，不难想到用桶记录每个数字的出现次数，只需要遍历数组找到比 aia_i 小的数即可。
但是这样仍然超时，继续优化。发现遍历数组时没必要全遍历一边，只需要遍历到 n\sqrt{n} 即可。
注意以下几点：
-
对于完全平方数，n\sqrt{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;
}
|
