OI题库

【问题描述】

两个d维向量A=[a₁，a₂，…，a_d]与B=[b₁，b₂，…，b_d]的内积为其相对应维度的权值的乘积和，即：

(A，B)=sum(a_ib_i)(1<=i<=d)=a₁b₁+a₂b₂+…+a_db_d
现有n个d维向量x₁…，x_n，小喵喵想知道是否存在两个向量的内积为k的倍数。请帮助她解决这个问题。

【输入格式】
输入文件meow.in的第一行包含3个正整数n，d，k，分别表示向量的个数，维数以及待检测的倍数。
接下来n行每行有d个非负整数，其中第i行的第j个整数表示向量xi的第j维权值x_i,j

【输出格式】
输出文件meow.out包含两个整数，用空格隔开。
如果存在两个向量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

【样例说明】
(x1,x2)=1
(x1,x3)=1
(x2,x3)=2

【数据规模】

测试点编号	n	d	k	xi,j
1	2	20	2	<=10
2	5	20	2	<=10
3	10	20	3	<=10
4	20	20	2	<=100
5	50	20	3	<=100
6	50	50	2	<=1000
7	50	50	3	<=3000000
8	80	80	2	<=2000000
9	100	100	3	<=3000000
10	500	100	3	<=3000000
11	1000	100	2	<=2000000
12	1000	100	3	<=3000000
13	10000	100	2	<=10
14	10000	100	3	<=10
15	15000	100	2	<=10
16	18000	100	2	<=10
17	20000	100	2	<=10
18	50000	30	3	<=10
19	80000	30	3	<=10
20	100000	30	3	<=10