Divide Sum 比赛时竟然想不出。。。。。。。

Divide Sum

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

SubmitStatus

Problem Description

long long ans = 0;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
ans += a[i] / a[j];
给出n,a[1]...a[n],求ans

Input

不超过5组数据，每组数据：

第一行n(1 <= n <= 10^5)

第二行n个数，a[1].. a[n] (1 <= a[i] <= 10^5)

Output

每组数据一行，ans

Sample Input

5
1 2 3 4 5

Sample Output

27

如此做法复杂度为：
O(nlogn)=n/1+n/2+n/3+n/4+n/5+n/6+n/7+…………+n/n；

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <cmath>
 5 #include <algorithm>
 6 int a[100001],b[100001];
 7 long long ans,ans1;
 8 int main()
 9 {
10     int n,i,x,j,maxa;
11     while(~scanf("%d",&n))
12     {
13         memset(a,0,sizeof(a));
14         maxa=1;
15         for(i=0;i<n;i++)scanf("%d",&x),a[x]++,maxa=maxa>x?maxa:x;
16         b[0]=0;
17         for(i=1;i<=maxa;i++)
18         b[i]=b[i-1]+a[i];
19         ans=0;
20         for(i=1;i<=maxa;i++)
21         {
22             if(a[i])
23             {
24                 ans1=0;
25                 for(j=i-1;j<=maxa;j+=i)
26                 {
27                     ans1+=n-b[j];
28                 }
29                 ans+=ans1*a[i];
30             }
31         }
32         printf("%lld
",ans);
33     }
34 }

View Code