Boring Sum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 814 Accepted Submission(s):
390
boring.
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.
In 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.
给出n个数的数列a,bi的取值为在1 <= j < i之间如果存在aj % ai == 0,
则取最大下标的值赋给bi,如果不存在,则bi = ai;ci的取值为在i < j <= n之间
如果存在aj % ai == 0,则取最小下标值赋给bi,如果不存在,则ci = ai。
求b1 * c1 + b2 * c2 + ... + bn * cn的和。
思路:
如果直接暴力的话一定会超时,所以我们可以开一个vis数组来记录每一个值
所对应的最大的下标是多少。即每查找ai,分解出ai的质因子,更新vis数组
#include<stdio.h>
#include<string.h>
#define ll __int64
#define maxn 100000+5
#define mem(x) memset(x,0,sizeof(x)) ll a[maxn],b[maxn],c[maxn],sum,n;
ll vis[maxn];//a[i]的下标i int main()
{
ll i,j,k,temp;
while(scanf("%I64d",&n),n)
{
mem(b);
mem(c);
mem(vis);
for(i=;i<=n;i++)
scanf("%I64d",&a[i]);
vis[a[]]=;
for(i=;i<=n;i++)
{
for(j=;j*j<=a[i];j++)
{
if(a[i]%j!=) continue;//取质因子 // printf("i=%I64d j=%I64d a[i]=%I64d ",i,j,a[i]); if(vis[j]!=)//
{
b[vis[j]]=a[i];
// printf("b[vis[j]]=%I64d vis[j]=%I64d ",b[vis[j]],vis[j]);
vis[j]=;
}
temp=a[i]/j;
// printf("temp=%I64d ",temp);
if(vis[temp]!=)//更新
{
b[vis[temp]]=a[i];
// printf("b[vis[temp]]=%I64d vis[temp]=%I64d",b[vis[temp]],vis[temp]);
vis[temp]=;
}
// printf("\n");
}
vis[a[i]]=i;
}
for(i=;i<=n;i++)
if(b[i]==)
b[i]=a[i];
mem(vis);
vis[a[n]]=n; for(i=n-;i>=;i--)
{
for(j=;j*j<=a[i];j++)
{
if(a[i]%j!=) continue;//取质因子
if(vis[j]!=)//
{
c[vis[j]]=a[i];
vis[j]=;
}
temp=a[i]/j;
if(vis[temp]!=)//更新
{
c[vis[temp]]=a[i];
vis[temp]=;
}
}
vis[a[i]]=i;
}
for(i=;i<=n;i++)
if(c[i]==)
c[i]=a[i];
// for(i=1;i<=n;i++)
// printf("b:%I64d\tc:%I64d\n",b[i],c[i]);
sum=;
for(i=;i<=n;i++)
sum+=b[i]*c[i];
printf("%I64d\n",sum);
}
return ;
}