1. 首页
  2. 代码宅, 数学问题

【Road】

【问题描述】

给出n个数a1~an,询问有多少三元组(i,j,k)满足一下两个条件:

条件一:i<j<k。

条件二:ai*aj*ak是p的倍数。

【输入格式】

第一行两个数n和p。

接下来一行n个数a1~an。

【输出格式】

一行一个数ans,表示多少个三元组(i,j,k)满足条件。

【输入样例1】

4 100

4 5 2 5

【输出样例1】

2

【输入样例2】

12 1

1 1 1 1 1 1 1 1 1 1 1 1

【输出样例2】

220

【输入样例3】

27 360
269 154 94 221 171 154 50 210 258 358
121 159 8 47 290 125 291 293 338 248
295 160 268 227 99 4 273

【输出样例3】

114

【数据范围】

对于100%的数据 n≤30000 1≤ai≤10^8 1≤p≤10^6

总结回家再写 

首先对于三个数a b c 如果它们相乘能够成为P的倍数,那么gcd(a,P)*gcd(b,P)*gcd(c,P)一定是P的倍数。

所以,先计算出P的所有约数,再记录对于每个a[i],gcd(a[i],P)出现的次数。

之后枚举约数,如果是三个相等的约数且这个约数出现次数大于等于3 那么它的组合方案就有x*(x-1)*(x-2)/6种

如果有两个是一样的那么就是x*[y*(y-1)/2]种

如果三个都不一样就是x*y*z种

因为P最大只有10^6  可证(da)明(biao)得约数个数不会超过240 于是稳稳的240^3的复杂度过掉这道题。

 

评分 5.00, 满分 5 星
1
0
看完收藏一下,下次也能找得到
上一篇:
:下一篇

发表评论

gravatar

*

沙发空缺中,还不快抢~