4146: [AMPPZ2014]Divisors
Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 211 Solved: 139
[Submit][Status][Discuss]
Description
Input
第一行包含一个正整数n(1<=n<=2000000)，表示序列长度。
第二行包含n个正整数，依次表示a[1],a[2],...,a[n](1<=a[i]<=2000000)。
Output
一个整数，即满足条件的二元组的个数。
Sample Input
5
2 4 5 2 6
2 4 5 2 6
Sample Output
6
HINT
满足条件的6组分别为(1,2),(1,4),(1,5),(4,1),(4,2),(4,5)。
Source
感觉也只有我这种数学盲才会做这种题目都要看题解
做完题想了一想这不是个大暴力吗
记录一下每个数有多少个。。然后对他本身和他的倍数求一下组合就好了。。。（语文不好说不清楚）
复杂度好像可以证明是log级别的。。。我也不是很清楚
细节：答案可能是long long
#include <cstdio>
#include <algorithm>
using namespace std;
int c[2000010],n,x,Max;
long long ans;
int read(){
int x = 0,f = 1,c = getchar();
while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
int main(){
n = read();
for (int i=1;i<=n;i++){
x = read();Max = max(Max,x);
c[x]++;
}
for (int i=1;i<=Max;i++)
if (c[i]){
ans+=1LL*c[i]*(c[i]-1);
for (int j=2*i;j<=Max;j+=i) ans+=1LL*c[i]*c[j];
}
printf("%lld",ans);
}
评论 (0)
