首页 > 题解 > codeforces 457D CGCDSSQ

codeforces 457D CGCDSSQ

全是公式懒得搬了= =

地址

题解

$f[i][x]$表示以$i$为左端点的区间中,$gcd=x$的有多少个。

由右到左进行转移,赋初值$f[i][a_i]=1$:

$f[i][gcd(x,a_i)]=\sum f[i+1][x]$

因为对于以$a_i$为左端点的区间$gcd$,最多只有$log_a_i$种取值(每次$gcd$至少减小一半),所以第二维其实只有$log_a_i$个有值。我们可以用map代替第二维,并滚动第一维。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×