#6487. 基础 FFT 练习题

内存限制:1024 MiB 时间限制:70 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给定两个长度都为 n 的正整数数组 a_{1},a_{2},...,a_{n},b_{1},b_{2},...,b_{n} ,求:

\sum_{i=1}^{n} \sum_{j=1}^{n} \left\lfloor \sqrt{\lvert a_{i}-b_{j}\rvert} \right\rfloor

其中 \lfloor \rfloor 表示下取整。

输入格式

第一行包含一个正整数 C ,表示数据组数。

每组数据第一行包含一个正整数 n ,表示数组的长度。

第二行包含 n 个正整数,依次表示 a_{1},a_{2},...,a_{n}

第三行包含 n 个正整数,依次表示 b_{1},b_{2},...,b_{n}

输出格式

对于每组数据输出一行一个整数,即答案。

样例

样例输入

2
3
1 2 1
4 5 3
3
2 5 1
1 3 3

样例输出

11
9

数据范围与提示

输入数据保证: 1 \le C \le 10 1 \le n \le 10^5 \sum_{i=1}^{n} a_{i} \leq 10^6,\sum_{i=1}^{n} b_{i} \leq 10^6

注:数据是随机生成的,不保证一定很强力。时间限制较严格,大部分非标程算法会被卡掉。

题目原作者

Claris