题目地址：HDU 4961
看来这题的测试数据是随机的。不然出了极限数据还真过不了。。。这题我的方法是建一个哈希结构体，记录两个变量，分别是num位置，然后是f，f==0表示这个数没出现过，f==1表示这个数出现过。然后分别从前面和后面扫一遍。每次扫的时候，对每一个出现的数都进行标记。然后对当前的数枚举该数的倍数，全部枚举完，取位置num最大的。然后找完之后，对哈希结构体进行更新。如果前面曾经出现过的话，就直接换掉，因为后面的数总比前面的更优。最后扫完两遍之后两个数组就能求出来了。计算就行了。
代码如下：
#include <cstring>
#include <cstdio>
#include <math.h>
#include <algorithm>
using namespace std;
#define LL __int64
struct node
{
LL num, f;
}_hash[110000];
LL a[110000], b[110000], c[110000];
int main()
{
LL n, i, j, sum, max1, mmax;
LL ans;
while(scanf("%I64d",&n)!=EOF&&n)
{
max1=-1;
for(i=1;i<=n;i++)
{
scanf("%I64d",&a[i]);
if(max1<a[i])
max1=a[i];
}
for(i=1;i<=max1;i++)
_hash[i].f=0;
for(i=1;i<=n;i++)
{
mmax=-1;
for(j=a[i];j<=max1;j+=a[i])
{
if(_hash[j].f)
{
if(mmax<_hash[j].num)
{
mmax=_hash[j].num;
}
}
}
_hash[a[i]].f=1;
_hash[a[i]].num=i;
if(mmax==-1)
b[i]=a[i];
else
b[i]=a[mmax];
}
for(i=1;i<=max1;i++)
_hash[i].f=0;
for(i=n;i>=1;i--)
{
mmax=1e7;;
for(j=a[i];j<=max1;j+=a[i])
{
if(_hash[j].f)
{
if(mmax>_hash[j].num)
{
mmax=_hash[j].num;
}
}
}
_hash[a[i]].f=1;
_hash[a[i]].num=i;
if(mmax==1e7)
c[i]=a[i];
else
c[i]=a[mmax];
}
ans=0;
for(i=1;i<=n;i++)
{
ans+=b[i]*c[i];
//printf("b==%d c==%d\n",b[i],c[i]);
}
printf("%I64d\n",ans);
}
return 0;
}HDU 4961(杭电多校#9 1002题)Boring Sum（瞎搞）,布布扣,bubuko.com
HDU 4961(杭电多校#9 1002题)Boring Sum（瞎搞）
原文：http://blog.csdn.net/scf0920/article/details/38686099