题目详情题解（0）讨论（0）提交记录（0）

AT_abc133_b.[ABC133B] Good Distance

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在 DD 维空间中有 NN 个点。

第 ii 个点的坐标为 (Xi1, Xi2, ..., XiD)(X_{i1},\ X_{i2},\ ...,\ X_{iD})。

坐标为 (y1, y2, ..., yD)(y_1,\ y_2,\ ...,\ y_D) 的点与坐标为 (z1, z2, ..., zD)(z_1,\ z_2,\ ...,\ z_D) 的点之间的距离为 (y1−z1)2+(y2−z2)2+...+(yD−zD)2\sqrt{(y_1 - z_1)^2 + (y_2 - z_2)^2 + ... + (y_D - z_D)^2}。

请问有多少组 (i, j)(i,\ j) 满足 i<ji < j，使得第 ii 个点与第 jj 个点之间的距离为整数。

输入格式

输入以如下格式从标准输入中给出。

NN DD
X11X_{11} X12X_{12} ... X1DX_{1D}
X21X_{21} X22X_{22} ... X2DX_{2D}
⋮\vdots
XN1X_{N1} XN2X_{N2} ... XNDX_{ND}

输出格式

输出满足第 ii 个点与第 jj 个点之间的距离为整数的 (i,j)(i, j) 组数（i<ji < j）。

输入输出样例

  • 输入#1

    3 2
1 2
5 5
-2 8

    输出#1

    1

  • 输入#2

    3 4
-3 7 8 2
-12 1 10 2
-2 8 9 3

    输出#2

    2

  • 输入#3

    5 1
1
2
3
4
5

    输出#3

    10

说明/提示

限制条件

  • 所有输入均为整数。
  • 2≤N≤102 \leq N \leq 10
  • 1≤D≤101 \leq D \leq 10
  • −20≤Xij≤20-20 \leq X_{ij} \leq 20
  • 不会有相同坐标的点。即对于 i≠ji \neq j，存在某个 kk 使得 Xik≠XjkX_{ik} \neq X_{jk}。

样例解释 1

如下有 11 组点对的距离为整数。

  • 第 11 个点与第 22 个点的距离为 ∣1−5∣2+∣2−5∣2=5\sqrt{|1-5|^2 + |2-5|^2} = 5，是整数。
  • 第 22 个点与第 33 个点的距离为 ∣5−(−2)∣2+∣5−8∣2=58\sqrt{|5-(-2)|^2 + |5-8|^2} = \sqrt{58}，不是整数。
  • 第 33 个点与第 11 个点的距离为 ∣−2−1∣2+∣8−2∣2=35\sqrt{|-2-1|^2 + |8-2|^2} = 3\sqrt{5}，不是整数。
首页