UOJ Logo ydc的博客

博客

noip 2014 day2 T3 ydc题解

2014-11-09 14:33:07 By ydc

一个$O(nm)$的做法是枚举并在模意义下验根,但是单纯这么做几乎不可能过

容易证明对于原方程的一个根$x$,必有$x|a_0$

$a_0$在$[1,m]$内的约数个数不会特别多,我们如果能做到只对他的约数验根,那么验根的时间是能够承受的,于是瓶颈在于找$[1,m]$内的所有约数

利用筛法的思想,我们找所有形如$p^k$,$p$为质数的不能被$a_0$整除的数,将他们的倍数筛去。

$a_0$的指数和当然不会太大,我们真正的瓶颈在于——对于每个质数,要试验他是否是$a_0$的约数

记$\pi(n)=n/ln(n),L=\lg a_0$,这样的时间复杂度是$O(L\pi(n))$的,显然过不去

压位大法好,第一反应是压9位

int sum=0;
for(int i=1;i<=n;++i)
    sum=((LL)sum*1000000000+a[i])%p;

可以判断$p$是否是$a_0$的约数

但是这样子经实测仍然过不了

如果压18位的话

int sum=0;
for(int i=1;i<=n;++i)
    sum=((LL)sum*1000000000000000000LL+a[i])%p;

乘的是个常数,我们完全可以预处理一个变量表示$10^{18} \mod p$

这样子的复杂度是$O(L\pi(n)/18)$,我考试的时候本机跑$(x-10^{100})^{100}$是0.8s多接近0.9s也许会挂

考完之后zty告诉我说,对于大于$10^5$的质数,筛去他的倍数意义不大,那么我们调一下筛的大小,只筛$10^5$以内的约数,超过$10^5$以内不能被$a_0$整除的质数(以及他们影响到的数)还是用验根的方法,用这个常数优化就能比较快的出解了

UPD:

已挂

不过我们还有70分!

ydc个逗逼,滚粗了

评论

vfleaking
前排
Gromah
表示只会50分
keavil
你写了我就不写啦

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。