#P13947. [2024多校联盟省选模拟]图图

    ID: 13159 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600数论莫比乌斯反演组合数学构造模拟前缀和差分

[2024多校联盟省选模拟]图图

题目描述

黑暗中的魔神小 O 穿越到了一个新世界,这是一个充满元素反应的开放世界,小 O 想图图了。

这个世界有 nn 种元素,编号 11 到 nn。第 ii 号元素的特征数值为 aia_i,其中 ai∈[1,m]a_i\in[1,m] 且互不相同。

当 xx 号元素与 yy 号元素相遇(x≠yx\ne y)时,会发生编号为 gcd⁡(ax,ay)\gcd(a_x,a_y) 的反应。反应由一个 0101 序列 hh 描述:若 hi=1h_i=1,则特征数值较大的元素克制较小的;若 hi=0h_i=0 则相反。

称存在一组三角克制关系,若有三个互不相同的元素 x,y,zx,y,z 满足:xx 克制 yy,yy 克制 zz,zz 克制 xx。

你需要计算这样的无序三元组 (x,y,z)(x,y,z) 的数量,并输出任意一组。注意 (x,y,z)(x,y,z)、(y,z,x)(y,z,x)、(z,x,y)(z,x,y) 算同一组。

输入格式

  • 第一行两个整数 n,mn,m。
  • 第二行 mm 个整数(00 或 11),第 ii 个整数表示 hih_i。
  • 第三行 nn 个整数,第 ii 个整数表示 aia_i。

输出格式

  • 第一行一个整数:三角克制关系总数。
  • 第二行三个整数 x,y,zx,y,z: 需满足 xx 克制 yy,yy 克制 zz,zz 克制 xx。
4 6
1 1 0 0 0 0
3 4 5 6
2
1 4 2

样例解释(样例 1)

给出的克制关系中,可以发现只有 (1,4,2)(1,4,2) 与 (1,4,3)(1,4,3) 两组三角关系。

数据范围与提示

  • 对于 100%100\% 的数据:4≤n≤1064\le n\le 10^6,n≤m≤2×106n\le m\le 2\times 10^6,hi∈{0,1}h_i\in\{0,1\},1≤ai≤m1\le a_i\le m,保证 aia_i 互不相同,且一定存在三角克制关系。
测试点 n≤n\le m≤m\le 特殊限制
1–4 3000 10000 无
5 5000 A
6 无
7 10510^5 2×1052\times 10^5 A
8 B
9–10 无
11–12 10610^6 2×1062\times 10^6 A
13–14 B
15–20 无

特殊限制:

  • A:∀i>1, hi=0\forall i>1,\ h_i=0。
  • B:hi≡i(mod2)h_i\equiv i\pmod 2。