Boring Sum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 446 Accepted Submission(s): 227
Here is the problem. Given an integer sequence a1, a2, …, an, let S(i) = {j|1<=j<i, and aj
is a multiple of ai}. If S(i) is not empty, let f(i) be the maximum integer in S(i); otherwise, f(i) = i. Now we define bi as af(i). Similarly, let T(i) = {j|i<j<=n,
and aj is a multiple of ai}. If T(i) is not empty, let g(i) be the minimum integer in T(i); otherwise, g(i) = i. Now we define ci
as ag(i). The boring sum of this sequence is defined as b1 * c1 + b2
* c2 + … + bn * cn.
Given an integer sequence, your task is to calculate its boring sum.
Each case consists of two lines. The first line contains an integer n (1<=n<=100000). The second line contains n integers a1, a2, …, an
(1<= ai<=100000).
The input is terminated by n = 0.
5 1 4 2 3 9 0
136HintIn the sample, b1=1, c1=4, b2=4, c2=4, b3=4, c3=2, b4=3, c4=9, b5=9, c5=9, so b1 * c1 + b2 * c2 + … + b5 * c5 = 136.
#include<stdio.h>
#include<string.h>
__int64 fact[100005][129],k[100005];
void setprim()
{
memset(k,0,sizeof(k));
for(__int64 i=1;i<=100000;i++)
{
for(__int64 j=i;j<=100000;j+=i)
{
fact[j][++k[j]]=i;
}
}
}
__int64 a[100005],b[100005],c[100005],index[100005];
int main()
{
setprim();
__int64 i,j,sum,n;
while(scanf("%I64d",&n)>0&&n)
{
for( i=1;i<=n;i++)
scanf("%I64d",&a[i]);
memset(index,0,sizeof(index));
for(i=1;i<=n;i++)
{
if(index[a[i]])b[i]=a[index[a[i]]];
else b[i]=a[i];
for(j=1;j<=k[a[i]];j++)
index[fact[a[i]][j]]=i;
}
sum=0;
memset(index,0,sizeof(index));
for(i=n;i>=1;i--)
{
if(index[a[i]])c[i]=a[index[a[i]]];
else c[i]=a[i];
for(j=1;j<=k[a[i]];j++)
index[fact[a[i]][j]]=i;
}
for( i=1;i<=n;i++)
sum+=b[i]*c[i];
printf("%I64d\n",sum);
}
}