首页 > 代码库 > Divide Sum 比赛时竟然想不出。。。。。。。

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

2024-07-15 03:57:37   225人阅读

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

51 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\n",ans);33     }34 }
View Code

 


联系
我们