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);
        }
}