坏心情消除计划题解

当n=2时,我们该怎么做呢?
设p=a[1],q=a[2]
p和q能组成的数是py+qz,y和z都是整数,将gcd(p,q)提出来,py+qz=gcd(p,q)*(yp0+zq0),其中gcd(p0,q0)=0,p0和q0可以通过更相减损得到1,也就是说(yp0+zq0)可以等于任意整数,因此py+qz可以得到任意gcd(p,q)的倍数。
所以可以用gcd(p,q)替换a[1]和a[2]。
推广到n=任意正整数,可以用gcd(a[1],a[2],...,a[n])替换掉a[1]到a[n]。
得到这个gcd,再与询问的x判断是否为倍数关系即可。
复杂度O(nlogn+T)

全部评论

相关推荐

把球:这个听过,你加了就会发现是字节的hr
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务