By

文章目录
  1. 1. 题意
  2. 2. 分析

原题

题意

题意非常绕的一个乱搞，对一个数组中的每个数求出在他前面，是他的倍数且靠他最近的一个bi，然后求出在他的后面，是他的倍数，且靠他最近的一个。

分析

逆向思维，从前往后和从后往前做两次处理，用标记数组，对每个数，将他质因子的标记数组值记为自己，打完表之后，直接求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/*
打表，逆向思维，倍数处理转化成质因数打表
wa:b[i]*c[i]本身可能爆long long。。。。。。。。
*/
#include <bits/stdc++.h>
using namespace std;
int a[100007],b[100007],c[100007],vis[100007];
int main()
{
    int n;
    while(scanf("%d",&n)&&n){
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++){
            if(vis[a[i]]){
                b[i]=a[vis[a[i]]];
            }
            else{
                b[i]=a[i];
            }
            for(int j=1;j*j<=a[i];j++){
                if(a[i]%j==0){
                    vis[j]=i;
                    vis[a[i]/j]=i;
                }
            }
        }
        memset(vis,0,sizeof(vis));
        for(int i=n;i>=1;i--){
            if(vis[a[i]]){
                c[i]=a[vis[a[i]]];
            }
            else{
                c[i]=a[i];
            }
            for(int j=1; j*j<=a[i]; j++){
                if(a[i]%j==0){
                    vis[j]=i;
                    vis[a[i]/j]=i;
                }
            }
        }
        long long sum=0;
        for(int i=1;i<=n;i++){
            sum+=(long long)b[i]*c[i];
        }
        printf("%I64d\n",sum);
    }
}
文章目录
  1. 1. 题意
  2. 2. 分析