ACdream 1071-不思議な%シリーズ

不思議な%シリーズ
Time Limit: 6000/3000MS (Java/Others) 
Memory Limit: 65536/32768KB (Java/Others)
Submit  Statistic  Next Problem
Problem Description
コンピューターの世界では、%はパーセンテージではなく、除法で余剰を取りますよ!
例:  4 % 2 = 0   5 % 3 = 2
君にあげる 2 ≤ N ≤ 100000 個数,a[1],a[2]...a[i]...a[n](1) ≤ a[i] ≤ 100000).
いくつかの組み合わせを聞きます (a[i], a[j]),(i != j, a[i]>a[j])は、 a[i] % a[j] != 0.
Input
複数セットのデータを入力します.(<= 30)
データのグループごとに:
1行目:N(表示 N )
2行目:N 個の要素 a[i]  
Output
出力にはいくつかの組み合わせがあります (a[i],a[j]) a[i] % a[j] != 0
Sample Input

3
1 1 1
4
1 2 3 4
5
1 2 2 4 6

Sample Output

0
2
1

Source
zju_xxx
Manager
admin

#include 
#include 
#include 
#include 
#include 

using namespace std;

#define ll long long
const int maxn=100009;
int x[maxn];
int tree[maxn];
int a[maxn];

int lowbit(int k)
{
    return k&(-k);
}

void add(int k)
{
    while(k0)
    {
        sum+=tree[k];
        k-=lowbit(k);
    }
    return sum;
}

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(x,0,sizeof x);
        memset(tree,0,sizeof tree);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            x[a[i]]++;
            add(a[i]);
        }
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            int cnt=0;
            for(int j=2*a[i];j<=100000;j+=a[i])
                cnt+=x[j];
            ans+=(n-getsum(a[i]))-cnt;
        }
        printf("%lld
",ans);
    }
    return 0;
}