题目描述
两个 d 维向量 A=[a1,a2,…,ad] 与 B=[b1,b2,…,bd] 的内积为其相对应维度的权值的乘积和,即:
$$(A,B)=\sum_{i=1}^d a_ib_i=a_1b_1+a_2b_2+\ldots+a_db_d
$$
现有 n 个 d 维向量 x1,…,xn ,小喵喵想知道是否存在两个向量的内积为 k 的倍数。请帮助她解决这个问题。
输入格式
第一行包含 3 个正整数 n,d,k,分别表示向量的个数,维数以及待检测的倍数。
接下来 n 行每行有 d 个非负整数,其中第 i 行的第 j 个整数表示向量 xi 的第 j 维权值 xi,j。
输出格式
包含两个整数,用空格隔开。
如果存在两个向量 xp,xq 的内积为 k 的整数倍,则输出两个向量的编号 p 与 q(要求 p<q)。如果存在多组这样的向量组合,输出其中任意一组即可。
若不存在这样的向量组合,则输出两个 −1。
3 5 2
1 0 1 0 1
1 1 0 1 0
0 1 0 1 1
2 3
提示
数据范围
测试点编号 |
n |
d |
k |
xi,j |
1 |
2 |
20 |
2 |
≤10 |
2 |
5 |
3 |
10 |
3 |
4 |
20 |
2 |
≤100 |
5 |
50 |
3 |
6 |
50 |
2 |
≤103 |
7 |
3 |
≤3×106 |
8 |
80 |
2 |
≤2×106 |
9 |
100 |
100 |
3 |
≤3×106 |
10 |
500 |
≤3×106 |
11 |
103 |
2 |
≤2×106 |
12 |
3 |
≤3×106 |
13 |
104 |
2 |
<10 |
14 |
3 |
15 |
1.5×104 |
2 |
16 |
1.8×104 |
17 |
2×104 |
18 |
5×104 |
30 |
3 |
19 |
8×104 |
20 |
105 |