j is a multiple of ai}. If T(i) is not empty, let g(i) be the minimum integer in T(i); otherwise, g(i) = i. Now we define ci as ag(i). The boring
sum of this sequence is defined as b1 * c1 + b2 * c2 + … + bn * cn.
Given an integer sequence, your task is to calculate its boring sum.
Input
The input contains multiple test cases.
Each case consists of two lines. The first line contains an integer n (1<=n<=100000). The second line contains n integers a1, a2, …, an (1<= ai<=100000).
The input is terminated by n = 0.
Output
Output the answer in a line.
Sample Input
5
1 4 2 3 9
0
Sample Output
136
題意:給你一個數組，讓你生成兩個新的數組，A要求每個數如果能在它的前面找個最近的一個是它倍數的數，那就變成那個數，否則是自己，C是往後找，輸出交叉相乘的和
思路：掃描記錄因子處理
#include
#include
#include
#include
#include
using namespace std;
typedef __int64 ll;
const int MAXN = 100005;
int a[MAXN], b[MAXN], c[MAXN], vis[MAXN];
int n;
int main() {
while (scanf("%d", &n) == 1) {
if (n == 0)
break;
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 <= (int)sqrt((double)a[i]+0.5); 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 <= (int)sqrt((double)a[i]+0.5); j++) {
if (a[i] % j == 0) {
vis[j] = i;
vis[a[i] / j] = i;
}
}
}
ll sum = 0;
for (int i = 1; i <= n; i++) {
sum += (ll)b[i] * c[i];
}
printf("%I64d\n", sum);
}
return 0;
}
