hud 4961 Boring Sum 数论(处理因子的方法)

题目链接:点击打开链接

题意:给出一个数列,每个数对应两个数,一个是右边第一个这个数本身的倍数还有左边.

思路:本来这个题一点思路都没有,因为看错题了,不过这个题有一个处理方法很好,可以学习一下

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
#define MAXN 100010
int f[MAXN],g[MAXN],a[MAXN],mark[MAXN];
vector <int> adj[MAXN];
void prepare()
{
        for(int i=1;i<MAXN;i++)
        {
                for(int j=1;j<MAXN/i;j++)
                {
                        adj[i*j].push_back(j);
                }
        }
}
int main()
{
        int n;
       //freopen("data.in","r",stdin);
       prepare();
        while(1){
                scanf("%d",&n);
                if(n==0) break;
                for(int i=1;i<=n;i++)
                {
                        scanf("%d",&a[i]);
                }
                memset(mark,0,sizeof(mark));
                for(int i=1;i<=n;i++)
                {
                        if(mark[a[i]]==0) f[i]=a[i];else f[i]=mark[a[i]];
                        for(int j=0;j<adj[a[i]].size();j++)
                        {
                                mark[adj[a[i]][j]]=a[i];
                        }
                }
                memset(mark,0,sizeof(mark));
                for(int i=n;i>0;i--)
                {
                        if(mark[a[i]]==0) g[i]=a[i];else g[i]=mark[a[i]];
                        for(int j=0;j<adj[a[i]].size();j++)
                        {
                                mark[adj[a[i]][j]]=a[i];
                        }

                }
                /*
                for(int i=1;i<=n;i++)
                {
                printf("%d %d %d %d\n",f[i],a[f[i]],g[i],a[g[i]]);
                }
                */
                long long ans=0;
                for(int i=1;i<=n;i++)
                {
                        ans+=(long long)f[i]*(long long)g[i];

                }
                printf("%I64d\n",ans);
        }
}