Boring Sum

5
1 4 2 3 9
0

136

Hint
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.
 

//203MS	8904K
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
vector<int>v[100007];
int a[100007],b[100007],c[100007],vis[100007];
int main()
{
    int n;
    for(int i=2;i<100007;i++)
    {
        for(int j=i;j<100007;j+=i)
            v[j].push_back(i);
    }
    while(scanf("%d",&n),n)
    {
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
        {
             if(!vis[a[i]])b[i]=a[i];
             else b[i]=vis[a[i]];
             vis[1]=a[i];          //因为打表的时候没有算上约数1，所以要加上
             for(int j=0;j<v[a[i]].size();j++)//更新a[i]的约数
                 vis[v[a[i]][j]]=a[i];
        }
        memset(vis,0,sizeof(vis));
        for(int i=n;i>=1;i--)
        {
             if(!vis[a[i]])c[i]=a[i];
             else c[i]=vis[a[i]];
             vis[1]=a[i];
             for(int j=0;j<v[a[i]].size();j++)
                 vis[v[a[i]][j]]=a[i];
        }
        __int64 ans=0;
        for(int i=1;i<=n;i++)
            ans+=(__int64)b[i]*(__int64)c[i];
        printf("%I64d\n",ans);
    }
    return 0;
}