坏心情消除计划题解

当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)

全部评论

相关推荐

生命诚可贵:先不说内容怎么样 排版就已经太差劲了 第一眼看不到重点,第二眼已经没有再看的耐心了, 篇幅占的太满了 字体不要用灰色 观感不好 想重点突出的黑色加粗就可以了 多列要点 少些大段的句子 项目经历把项目用的技术要点列出来,光写个python plc什么的太宽泛了 自我评价也有点偏多
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务