7
7
2015
0

BZOJ:4146: [AMPPZ2014]Divisors

4146: [AMPPZ2014]Divisors

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 211  Solved: 139
[Submit][Status][Discuss]

Description

给定一个序列a[1],a[2],...,a[n]。求满足i!=j且a[i]|a[j]的二元组(i,j)的个数。

 

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

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);
}
Category: BZOJ题解 | Tags: | Read Count: 420

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com