第K大公因子

/ 0评 / 0

筛法真是数论中的好东西,可以预处理方便大规模查询,比如今天做的第K大公因子

Problem Description

友谊度$friend(a,b)$是这么计算的:令$a, b$ 两个整数分别是两个同学的属性,两个同学的友谊度取决于 $a,b$ 第$k$ 大的公约数。如果不存在,就说明这两个同学之间完全没有友谊,友谊度为 $−1$。

Input

第一行是数据组数 $T (1≤T≤60)$。
对于每组数据:
第一行:首先是学生的数量 $n (1≤n≤10^5)$,约定的常数 $k (1≤k≤10^6)$。
第二行:$n$个整数,依次表示这些学生的属性值:$m_1,m_2,…,m_n (1≤m_i≤10^6)$。

Output

对于每组数据输出一行,以 Case x: 开头(x 表示数据编号,从 1 开始),后面是 n−1 个整数,分别是$friend(m_1,m_2),friend(m_2,m_3),…,friend(m_n−1,m_n)$,整数和整数之间用空格隔开。

Sample input

Sample output

Source 2017华东师范大学校赛K题

发表评论

电子邮件地址不会被公开。 必填项已用*标注