|
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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> using namespace std; #define MAXN 100005 int a[MAXN],b[MAXN],c[MAXN]; vector<int> d[MAXN]; void gen(){ for (int i = 1; i < MAXN; i++) { for (int j = 1; i * j < MAXN; j++) { d[i*j].push_back(i); } } } int vis[MAXN]; void solve(int n){ //-> memset(vis, -1, sizeof(vis)); for (int i = 1;i <= n; i++) { int now = a[i]; if (vis[now] != -1) { b[i] = vis[now]; } for (int j = 0;j < d[now].size(); j++) { vis[d[now][j]] = now; } if (b[i] == -1) { b[i] = now; } } //<- memset(vis, -1, sizeof(vis)); for (int i = n; i >= 1; i--) { int now = a[i]; if (vis[now] != -1) { c[i] = vis[now]; } for (int j = 0; j < d[now].size(); j++) { vis[d[now][j]] = now; } if (c[i] == -1) { c[i] = now; } } } int main(){ gen(); int n = 0; while(scanf(" %d",&n) != EOF && n){ memset(a, -1, sizeof(a)); memset(b, -1, sizeof(b)); memset(c, -1, sizeof(c)); for (int i = 1; i <= n; i++) { scanf(" %d",&a[i]); } solve(n); long long res = 0; for (int i = 1; i <= n; i++) { res += (long long)b[i] * (long long)c[i]; } printf("%lldn",res); } return 0; } |
智商鸿沟不可越系列。。。
思路是这样：首先对于1～100000每一个数生成一个约数表，方便以后查询，我们再建立一个int数组为vis，尺寸100000。接下来对于输入的数组，从左往右扫描，对于每一个数，如果vis[这个数]有值，说明当前数左端有倍数存在，最近的倍数就是这个vis值，没有的话，就是这个数本身，接下来读取当前数的每一个约数，对于每一个约数，当前数都是他们的倍数，所以更新vis[每一个约数]的值为当前数就可以了。
接下来方向反过来，从右到左扫描，算出c值，最统一出答案，小心别爆了int就行。