zcmimi's blog

arrow_back筛法共2篇文章

avatar
zc
2020-01-20 21:57:00
查看原题

点击跳转

结论:

x^{\frac14}内的因子筛掉,剩下的x一定是完全立方数或者不可化简

证明:

若存在p>x^{\frac14}b\times p^3=x,那么b>x^{\frac14}b=1

\because b>x^{\frac14} \therefore b\times p^3 >x,不符合

\therefore b=1,x为完全立方数

实现:

  1. 先晒出(10^{18})^{\frac14}(\approx31650)内的质数

  2. 筛掉x^{\frac14}内的因子,筛的过程中统计有没有立方

  3. 判断x是不是完全立方数(pow(x,1.0/3)^3+eps==x四舍五入)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先筛选出d_a,d_b,d_c

如果a,b,c的约数都不相同,那么ans = d_a \cdot d_b \cdot d_c

我们来考虑要减去的部分

(a,b,c) , (b,a,c)这样的是不符合的,减去其中一个

也就是减去d(gcd(a,b))\times(d(gcd(a,b)-1))

同理,(a,c,b),(c,b,a)也要减去.

这样的话会多减了一个d(gcd(a,b,c))*(d(gcd(a,b,c))-1),要加回来

...

https://www.luogu.com.cn/blog/lingchi/solution-cf1008d

1/1
Search
search