题意：给你一个数组，让你生成两个新的数组，A要求每个数如果能在它的前面找个最近的一个是它倍数的数，那就变成那个数，否则是自己，C是往后找，输出交叉相乘的和
分析：
这个题这种做法是O(n*sqrt(n))的复杂度，极限数据绝对会超时，但是这个题的数据有点水，所以可以过。
用vis【i】数组表示离数字 i 最近的倍数那个数在a【】中的位置，因为所有数字范围在1--100000所以可行 ，正着扫一遍，每次找到当前的数的除数，同时把除数覆盖位置，把 /除数 的数也覆盖位置。
倒着也是一样，找的是离这个数最近的倍数数字，然后相乘就行了。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #define LL __int64 8 const int maxn = 100000+10; 9 using namespace std; 10 LL a[maxn], pre[maxn], af[maxn], vis[maxn], sum; 11 12 int main() 13 { 14 int n, i, j, tmp; 15 while(~scanf("%d", &n) && n) 16 { 17 memset(af, 0, sizeof(af)); 18 memset(pre, 0, sizeof(pre)); 19 memset(vis, 0, sizeof(vis)); 20 for(i = 1; i <= n; i++) 21 scanf("%I64d", &a[i]); 22 for(i = 1; i <= n; i++) 23 { 24 if(vis[a[i]]) 25 pre[i] = a[vis[a[i]]]; 26 else 27 pre[i] = a[i]; 28 tmp = (int)sqrt(a[i]); 29 for(j = 1; j <= tmp; j++) 30 if(a[i]%j==0) 31 { 32 vis[j] = i; 33 vis[a[i]/j] = i; //一定不要忘了sqrt后面还有这个数的除数 34 } 35 } 36 37 memset(vis, 0, sizeof(vis)); 38 for(i = n; i >= 1; i--) 39 { 40 if(vis[a[i]]) 41 af[i] = a[vis[a[i]]]; 42 else 43 af[i] = a[i]; 44 tmp = (int)sqrt(a[i]); 45 for(j = 1; j <= tmp; j++) 46 if(a[i]%j==0) 47 { 48 vis[j] = i; 49 vis[a[i]/j] = i; 50 } 51 } 52 sum = 0; 53 for(i = 1; i <= n; i++) 54 sum += pre[i]*af[i]; 55 printf("%I64d\n", sum); 56 } 57 return 0; 58 }
hdu 4961 Boring Sum (思维 哈希 扫描)
原文：http://www.cnblogs.com/bfshm/p/3938052.html