数学真好玩
题意
现在有一个函数
要你求$f(x,y)(1\le x,y \le 10^{12})$。
题解
不考虑时间的复杂度我们可以发现在一段时间,$gcd(a,b)$是同一个数,而我们要做的就是快速找出这段时间,假设为最小$T$。
首先有$a=A\times \gcd(a,b)$,$b=B\times \gcd(a,b)$,$T$次过后$\gcd(a,b)$为$D\times \gcd(a,b)$,显然有$D|A$,并且有$(B-T)\%D=0$,在这当中,$T<D$恒成立,为何?假设$B=k\times D+T$,如果$T\ge D$那必定会有更小的$T’$,满足$B=(k+1)\times D+T’$。
那上式就相当于$T=B\%D$,那我们就需要找出这个最小的$D$,使得这个余数最小,而不难发现的是,$D$一定是$A$的素因子,为何?假设$D=p\times c$,余数为$x$,则$B=k\times D+x=k\times c\times p+x$;$D’=p$,余数为$y$,则$B=k’\times D’+y=k’\times p+y$。我们有$k’=\lfloor\frac{B}{p}\rfloor$,则肯定有$k\times c\le\lfloor\frac{B}{p}\rfloor$,即$k\times c\le k’$,则必有$x\ge y$。
所以我们只需要提前预处理出来$a$的质因子,至多只有$log(a)$个,而每次做完我们都需要$a/=gcd(a,b),b/=gcd(a,b)$,所以也是$log$级别的,那么最劣的复杂度就是$log(b)log(a)$。
代码
1 |
|
- 本文作者: baddog
- 本文链接: https://katoli.github.io/2022/06/24/EDU26/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!