数据前缀：draco。
题目描述
给定 $1$ 到 $N$ 的排列 $P=(P_1,\dots,P_N)$，统计满足 $1\le i\le j\le N$ 且 $\gcd(i,j)\ne 1$ 且 $\gcd(P_i,P_j)\ne 1$ 的整数对 $(i,j)$ 的个数。
输入格式
本题包含多组测试数据。
第一行一个整数 $T$（$1\le T\le 2 \times 10^4$），表示测试用例数。
对于每组测试用例：
- 第一行一个整数 $N$（$1\le N\le 3\times10^5$）；
- 第二行 $N$ 个整数 $P_1,\dots,P_N$，构成 $1\sim N$ 的一个排列。
保证 $\sum N \le 3\times10^5$（单文件内所有测试用例之和）。
输出格式
对每组测试用例输出一行一个整数，表示满足条件的整数对数量（包含 $i=j$ 的情况）。答案可能超过 32 位整数范围，请使用 64 位整数输出。
输入输出样例
样例 #1
样例输入 #1
2 6 5 1 3 2 4 6 12 1 2 3 4 5 6 7 8 9 10 11 12
样例输出 #1
6 32
样例 #2
样例输入 #2
1 1 1
样例输出 #2
0
样例 #3
样例输入 #3
2 3 1 2 3 4 4 3 2 1
样例输出 #3
2 2
样例 #4
样例输入 #4
5 30 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 30 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 30 2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15 18 17 20 19 22 21 24 23 26 25 28 27 30 29 30 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 1 2 3 4 5 6 7 8 9 10 30 17 4 29 12 1 26 9 22 15 30 7 20 3 24 11 28 5 18 13 2 27 8 21 16 25 6 19 10 23 14
样例输出 #4
187 60 60 146 142
数据范围
- $1\le T\le 2 \times 10^4$，$1\le N\le 3\times10^5$，$\sum N\le 3\times10^5$，$P$ 是 $1\sim N$ 的排列。
- 本题共 $100$ 个测试点。
$$ \begin{array}{|c|l|} \hline \text{测试点} & \text{性质} \\ \hline 1\sim10 & N\le 1000 \text{ 且 } \sum N \le 1600 \\ 11\sim35 & P_i=i \\ 36\sim45 & P_i=N-i+1 \\ 46\sim70 & T \le 30 \text{ 且 }\sum N\le 6\times10^4 \\ 71\sim100 & N\le 3\times10^5 \\ \hline \end{array} $$
背景（与题目没有任何关系）
数据范围也是极具艺术感：c 给到 1e9，集合却最多 3e5 个数，稀疏得像沙漠里撒了几粒芝麻；树只有 200 个节点，颜色却给到 1e6 种，颜色池大得能开染料厂，使用限制却抠门到每种最多用 n/3+1 次。这种反差让我一度怀疑出题人是不是在故意锻炼我的心理承受能力：先给我一个巨大的数字让我绝望，再悄悄告诉我“其实没那么大”，最后用测试点表格补一刀：“你看，我其实留了后门，只是你没找到”。 样例也是给得异常慷慨，第一题 8 个样例，从 n=1 到 c=1e9，跨度堪比从幼儿园到博士毕业；第三题 7 个样例，每个都解释得明明白白，生怕我看不懂题意。可样例多归多，数据范围大归大，两题还特意提醒“答案可能超过 32 位，请使用 64 位整数”，这种“温馨提示”让我瞬间清醒：原来出题人早就料到我可能会用 int128 然后爆掉，真是体贴入微。 最绝的是，四道题没有一个有故事背景，纯数学，纯抽象，纯考验耐心。我甚至开始怀念那些“小明要买苹果”“小猫要过河”的题了，至少我还能安慰自己是在解决生活问题。可在这里，我只能盯着“集合 S”“排列 P”“树 T”这些冰冷的符号，心想：出题人，您是不是把我当成了没有感情的计数机器？ 但冷静下来想想，出题人其实用心良苦：题面绕，是逼我细心读题；数据范围夸张，是让我学会分析复杂度；测试点表格详细，是给我留了骗分的活路；样例多，是怕我连题意都理解不了。这么一看，这哪里是比赛，分明是一场充满人文关怀的数学夏令营。感谢出题人，让我在考场上不仅锻炼了代码能力，还顺便复习了语文和排列组合 本回答由 AI 生成，内容仅供参考，请仔细甄别贡献说明
OpenAI Codex 协助补充样例与说明，使用暴力枚举核对新增样例答案，并完成输入合法性检查及测评数据包校验。