#P18713. Efficient Summation
Efficient Summation
Efficient Summation
对于正整数 ,将其质因数分解写为
$$y=\prod_{j=1}^{k}p_j^{\alpha_j},\qquad p_1<p_2<\cdots<p_k.$$给定一个长度为 、元素两两不同的序列 ,定义
如果 ,对应的因子 视为 。特别地,。这里的排名针对不同质因子按质数值递增排列后的顺序;某个质因子的指数会乘在该质数上。
给定上界 ,有 次查询。每次给出正整数 ,查询答案为
$$g(x)=\left(\sum_{i=1}^{\lfloor n/x\rfloor}f(ix)\right)\bmod 2^{32}.$$为了减少输出量,只需输出全部查询答案的按位异或。输入中的 以质因数分解形式给出。
输入格式
第一行包含三个整数 ,满足 、、。
第二行包含 个两两不同的整数 ,满足 。不保证 有序。
接下来 行分别描述一次查询。每行首先给出一个整数 ,随后给出 个整数 ,表示
是两两不同的质数,,保证 。 时表示 。
保证 。
输出格式
输出一行一个整数,表示全部 的按位异或,范围为 到 。先对每次查询的和取模,再异或。
原样例
10 2 5
2 3
0
1 5 1
1 2 1
1 7 1
2 2 1 3 1
31