社区讨论

Binary GCD 是可以 AC 的。

pplatelett
P5435基于值域预处理的快速 GCD参与者 12已保存回复 14

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
14 条
当前快照
1 份
快照标识符
@lo8u30sm
此快照首次捕获于
2023/10/28 00:34
2 年前
此快照最后确认于
2023/10/28 00:34
2 年前
查看原帖
Binary GCD 指的是按以下方法递归：
gcd⁡(a,b)={gcd⁡(∣a−b∣,min⁡(a,b))(a,b is odd)gcd⁡(a/2,b/2)(a,b is even)gcd⁡(a,b/2)(a is odd,b is even)gcd⁡(a/2,b)(a is even,b is odd)\gcd(a,b)=\begin{cases} \gcd(|a-b|,\min(a,b))&(a,b\text{ is odd})\\ \gcd(a/2,b/2)&(a,b\text{ is even})\\ \gcd(a,b/2)&(a\text{ is odd},b\text{ is even})\\ \gcd(a/2,b)&(a\text{ is even},b\text{ is odd}) \end{cases}
直接递归是过不了的，但实现好可以 <= 700ms 通过，附上代码：
CPP
int gcd(int a, int b) {
    int az = __builtin_ctz(a);
    int bz = __builtin_ctz(b);
    int z = min(az, bz);
    b >>= bz;
    while (a) {
        a >>= az;
        int diff = a - b;
        az = __builtin_ctz(diff);
        b = min(a, b), a = abs(diff);
    }
    return b << z;
}

回复

共 14 条回复，欢迎继续交流。

正在加载回复...