两个数组a和b
长度分别为n m
他们组成一个矩阵f fij=ai*bj
问这个矩阵中有多少个子矩阵里元素之和是c的倍数
输入格式

第一行一个正整数T(T<=20)，代表测试数据的组数。
每组数据有3行。
第一行三个正整数n,m,c
第二行有n个正整数a1,a2...,an
第三行有m个正整数b1,b2...,bm
数据范围：
1<=n,m<=30000
1<=ai,bi<=30000
1<=c<=30000


输出格式

每组数据输出一行。

输入样例
2
2 3 5
2 3
1 3 4
2 3 11
2 3
1 3 4
输出样例
6
0

讨论下，还没什么想法

看一下m和n  那么大  有没有nlogn及以下时间复杂度的算法
你那个已经超n^2了
        设sumA[i]表示数组a前i项和，sumB[i]表示数组b前i项的和。
    递推可得以(i,j)为左上顶点，(x,y)为右下顶点的子矩阵，它的所有元素之和为(sumA[x]-sumA[i-1])*(sumB[y]-sumB[j-1])。
    枚举所有(x,i)求出(sumA[x]-sumA[i-1])%c的值，用hashA记录，hashA[k1]表示(sumA[x]-sumA[i-1])%c=k1的(x,i)有多少对。
    枚举所有(y,j)求出(sumB[y]-sumB[j-1])%c的值，用hashB记录，hashB[k2]表示(sumA[y]-sumA[j-1])%c=k2的(y,j)有多少对。
    暴力枚举k1,k2，若k1*k2%c=0，那么答案加上hashA[k1]*hashB[k2]。
    时间复杂度为O(n^2+c^2)。
对上面进行优化，假设枚举k1，设gcd(k1,c)=d，d’=c/d，那么k2必须是d’的倍数才会使得k1*k2%c=0，所以第二维只要枚举d’、2*d’、3*d’……即可，其实就是一个筛法的应用。复杂度为O(n^2+ clogc)。

还是学校oj。。。有人说CF上有类似的
原题： LRC是SCAU_ACM校队的主席，职业生涯为校队作过很多贡献。除此之外，LRC也被各路ACMER奉为RP之神，源于以下两件事：
        1．曾用随机算法以1/(50^100)概率AC了一道dp题；
        2．省赛抽奖现场以1/600概率抽中特等奖获得一个4T的SSD。
    但大家不知道，LRC有一个测试当天RP值的奇葩方法。首先，用随机算法random出一个长度为n的数组a1,a2...,an；然后，再用随机算法random出一个长度为m的数组b1,b2...,bm；紧接着，依然是用随机算法random出一个正整数c；
接下来，LRC可以得到一个n*m的矩阵F，使得矩阵中的每个元素Fij=ai*bj；最后，计算一下F有多少个子矩阵，它的各个元素之和被c整除，那么这个值，就是他的RP值。
    现在LRC将所有的数random出来了，他想让未来校队的大神，也就是你，计算一下他的RP值。



输入格式

第一行一个正整数T(T<=20)，代表测试数据的组数。
每组数据有3行。
第一行三个正整数n,m,c
第二行有n个正整数a1,a2...,an
第三行有m个正整数b1,b2...,bm
数据范围：
1<=n,m<=30000
1<=ai,bi<=30000
1<=c<=30000


输出格式

每组数据输出一行。
输出一个数，代表LRC的RP值。


输入样例

2
2 3 5
2 3
1 3 4
2 3 11
2 3
1 3 4



输出样例

6
0

被好几道给卡了

没人。。。。。。