网站建设价格由什么决定,南京学做网站,wordpress放入视频链接,广告网架wmq的AB Problem 发布时间: 2017年4月9日 17:06 最后更新: 2017年4月9日 17:07 时间限制: 3000ms 内存限制: 512M 描述 这是一个非常简单的问题。 wmq如今开始学习乘法了#xff01;他为了训练自己的乘法计算能力#xff0c;写出了n个整数#xff0c;并且对每两个数a,…
wmq的A×B Problem 发布时间: 2017年4月9日 17:06 最后更新: 2017年4月9日 17:07 时间限制: 3000ms 内存限制: 512M
描述 这是一个非常简单的问题。 wmq如今开始学习乘法了他为了训练自己的乘法计算能力写出了n个整数并且对每两个数a,b都求出了它们的乘积a×b。现在他想知道在求出的n(n−1)2个乘积中除以给定的质数m余数为k(0≤km)的有多少个。 输入 第一行为测试数据的组数。 对于每组测试数据第一行为2个正整数n,m,2≤n,m≤60000分别表示整数的个数以及除数。 接下来一行有n个整数满足0≤ai≤109。 保证总输出行数∑m≤3×105。 输出 对每组数据输出m行其中第i行为除以m余数为(i−1)的有多少个。 样例输入1 复制 2
4 5
2 0 1 7
4 2
2 0 1 6 样例输出1 3
0
2
0
1
6
0 提示 对于第1组样例求出的乘积为0,0,0,2,7,14因而除以5余数为0的有3个余数为1的有0个余数为2的有2个余数为3的有0个余数为4的有1个。 标签 数论 来源 北方大学 ACM多校训练 第六场t 题解
将给出的数m求其原根记为w然后将n个数都表示为w的幂的形式这样的话两数相乘再取模的操作就变成了两幂相加为定值的情况了。
根据两数的幂和为一定值想到卷积的性质。
