acdream Divide Sum

Divide Sum

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

Submit Statistic Next Problem

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

用 n/i = n/(i+k)的方法找上届和下届，统计出现次数，超时。
贴一个代码：

 1 /* 
 2 * this code is made by 987690183 
 3 * Problem: 1181 
 4 * Verdict: Time Limit Exceeded 
 5 * Submission Date: 2014-09-01 12:47:21 
 6 * Time: 1000MS 
 7 * Memory: 2848KB 
 8 */
 9 #include<iostream> 
10 #include<stdio.h> 
11 #include<cstring> 
12 #include<cstdlib> 
13 using namespace std; 
14   
15 int date[100002]; 
16 int num[100002]; 
17 int sum1[100002]; 
18 int main() 
19 { 
20     int n; 
21     int maxn; 
22     while(scanf("%d",&n)>0) 
23     { 
24         memset(num,0,sizeof(num)); 
25         maxn = -1; 
26         for(int i=1;i<=n;i++) { 
27                 scanf("%d",&date[i]); 
28                 num[date[i]] ++; 
29                 if(date[i]>maxn) maxn = date[i]; 
30         } 
31         sum1[0]=0; 
32         for(int i=1;i<=maxn;i++) 
33         sum1[i] = sum1[i-1]+num[i]; 
34   
35         long long sum = 0; 
36         if(n>900) 
37         for(int i=1;i<=maxn;i++) 
38         { 
39             if(num[i]>0) 
40             for(int j=1,la = 0;j<=i;j = la+1) 
41             { 
42                 la = i/(i/j); 
43                 sum = sum + (long long)(sum1[la]-sum1[j-1])*(i/j)*num[i]; 
44             } 
45         } 
46         else
47         { 
48             for(int i=1;i<=n;i++) 
49             { 
50                 for(int j=1;j<=n;j++) 
51                     sum = sum+date[i]/date[j]; 
52             } 
53         } 
54         printf("%lld
",sum); 
55     } 
56     return 0; 
57 }

View Code

为什么超时，我很疑惑，因为最坏的情况下1-10^5个数字，只出现一次。

时间应该也是n*sqrt(n);

和ac代码比较也是一样吧。超时代码唯一不同的是有许多*，/的运算。

ac代码：只有+

思路：统计数字x的出现次数num[]，然后求前n项和用sum1[]保存

然后改变一下思路，求对于第i个数字来说，被多少数字/过，

举例：i = 2，n =9；

那么首先[2-9]里的数字能除i+[8-9]能除i.这有数字8，9就算了两次。

知道统计第i个数字被多少数字/过，就不难理解。

 1 /* 
 2 * this code is made by 987690183 
 3 * Problem: 1181 
 4 * Verdict: Accepted 
 5 * Submission Date: 2014-09-01 14:41:17 
 6 * Time: 72MS 
 7 * Memory: 2848KB 
 8 */
 9 #include<iostream> 
10 #include<stdio.h> 
11 #include<cstring> 
12 #include<cstdlib> 
13 #include<math.h> 
14 using namespace std; 
15   
16 int date[100002]; 
17 int num[100002]; 
18 int sum1[100002]; 
19 int main() 
20 { 
21     int n; 
22     int maxn; 
23     while(scanf("%d",&n)>0) 
24     { 
25         memset(num,0,sizeof(num)); 
26         maxn = -1; 
27         for(int i=1;i<=n;i++) { 
28                 scanf("%d",&date[i]); 
29                 num[date[i]] ++; 
30                 if(date[i]>maxn) maxn = date[i]; 
31         } 
32         sum1[0]=0; 
33         for(int i=1;i<=maxn;i++) 
34         sum1[i] = sum1[i-1]+num[i]; 
35   
36         long long ans = 0; 
37         long long sum = 0; 
38         for(int i=1;i<=maxn;i++) 
39         { 
40             if(num[i]) 
41             { 
42                 ans = 0; 
43                 for(int j=i-1;j<=maxn;j=j+i) 
44                     ans = ans+n-sum1[j]; //！！！！
45                 sum = sum + ans*num[i]; 
46             } 
47         } 
48         printf("%lld
",sum); 
49     } 
50     return 0; 
51 }