主页 讨论版 问题 名次 状态 统计
欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~
问题 L: Simple Problem A

问题 L: Simple Problem A

时间限制: 3 Sec  内存限制: 128 MB
提交: 30  解决: 8
[提交][状态][讨论版]

题目描述

给定两个长度为n(1<= n <= 10,000)的数组:
    a[1]...a[n],(2 <= a[i] <= 100,000)
    c[1]...c[n],(0 <= c[i] <= 100,000)

对于其中的每一个元素a[i],假设存在两个数字b1,b2,
其中:
    b1为a[1]...a[i-1]中与a[i]不互质的最小数字,如果不存在为0;
    b2为a[1]...a[i-1]中与a[i]不互质的最大数字,如果不存在为0;

对于每一个元素a[i],我们要求的是res[i] = sum{val[k] | b1 <= k <= b2},输出res[i]的值;
其中val数组的值是动态变化的,一开始全为零,当我们计算完res[i]之后,我们要把c[i]加到val[a[i]]上去,然后进行计算,后续的计算也是采用同样的方式。

详细过程可以见样例。

输入

n    : 1 <= n <= 10,000
a[i] : 2 <= a[i] <= 100,000
c[i] : 0 <= c[i] <= 100,000
多组数据,处理到没有数据或者 n = 0 为止

输出

一行数字,res[1]...res[n],两个数字之间以空格隔开,行末没有空格。

样例输入

6
2 3 20 7 6 9
7 4 3 5 7 6
0

样例输出

0 0 7 0 19 11

提示

样例解释:

i = 1 : b1 = 0, b2 = 0,   res[1] = 0;                                      此时val[a[1]] += c[1], 即val[2] += 7;

i = 2 : b1 = 0, b2 = 0,   res[2] = 0;                                      此时val[a[2]] += c[2], 即val[3] += 4;

i = 3 : b1 = 2, b2 = 2;   res[3] = val[2] = 7;                         此时val[a[3]] += c[3], 即val[20] += 3;

i = 4 : b1 = 0, b2 = 0;   res[4] = 0;                                      此时val[a[4]] += c[4], 即val[7] += 5;

i = 5 : b1 = 2, b2 = 20; res[5] = val[2] + ... + val[20] = 19;  此时val[a[5]] += c[5], 即val[6] += 7;

i = 6 : b1 = 3, b2 = 6;   res[6] = val[3] + ... + val[6]  = 11;   此时val[a[6]] += c[6], 即val[9] += 6;



所以输出为 : 0 0 7 0 19 11

[提交][状态][讨论版]