Luogu5435 基于值域预处理的快速 GCD & Leetcode2543 - binary GCD -

题目链接：https://www.luogu.com.cn/problem/P5435

请忽略题目名称
学到一个科技：binary GCD，能够快速求出两个数 GCD（从这道题来看已经接近 \(O(1)\) 了）

代码：

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f;

int bin_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;
}

const int maxn=5005,mod=998244353;
int n,a[maxn],b[maxn],ans[maxn];
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)scanf("%d",&b[i]);
	
	for(int i=1;i<=n;i++){
		int cs = i, r=0;
		for(int j=1;j<=n;j++){
			(r += 1ll*cs*bin_gcd(a[i], b[j])%mod);
			if(r >= mod)r -= mod;
			cs = 1ll*cs*i%mod;
		}
		printf("%d\n",r);
	}

	return 0;
}

利用这个思想来看 Leetcode 双周赛的 T4：

结论：如果 \(gcd(a,b)\) 是 \(2^k\) 就 true 否则 false
考虑倒推，如果 \(x,y\) 都是偶数，那么都除以 2 即可，\(gcd\) 多一个 2
如果一奇一偶，那显然除以一个 2 不影响 gcd，
否则，\((x,y) \rightarrow (x,x+y) \rightarrow (x,\frac{x+y}{2})\) （不妨设 \(x < y\)）
如果 \(x==y\) 且均为奇数，那么只能是最终态 \((1,1)\)
注意到只有两个偶数的时候会改变 gcd