AT3645 GCDロボット

思路

根据题意，自然要求 $\gcd(A_i , Z)$ ，记为 $B_i$

显然 ， 与 $Z$ “完全一样”的数一定要是每一个 $B_i$ 的倍数。

很显然， $Z$ 的最小取值为 $\operatorname{lcm}(Ans , B_i)$ （Ans 是答案，初值为 $1$）。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500010;

__int128_t N , Z , A[MAXN] , B[MAXN] , S = 1;

template<class T>
T Gcd(T X , T Y) {
	while(Y ^= X ^= Y ^= X %= Y);
	return X;
}

template<class T>
void Write(T x) {
	if(x < 0) {
		putchar('-');
		x *= -1;
	}
	if(!x) return;
	Write(x / 10);
	putchar(x % 10 + '0');
}

template<class T>
inline void read(T &ret) {
	ret = 0;
	short f = 1;
	char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c <= '9' && c >= '0') {
		ret = (ret << 3) + (ret << 1) + c - 48;
		c = getchar();
	}
}

template<class T>
inline T Lcm(T x , T y) {
	return x / Gcd(x , y) * y;
}

int main() {
	ios::sync_with_stdio(false);
	
	read(N);
	read(Z);
	
	for(int i = 1; i <= N; i++) read(A[i]);
	
	for(int i = 1; i <= N; i++) B[i] = Gcd(A[i] , Z);
	
	for(int i = 1; i <= N; i++) S = Lcm(S , B[i]);
	
	Write(S);
	
	return 0;
}