Gcd小练习(LuoGu)

1.P1372 又是毕业季I

[ 1 , n ] [1,n] [1,n]选k个数使 g c d gcd gcd最大。

​ 考虑答案为 x x x， x x x满足 n x ≥ k \dfrac{n}{x}\ge k xn​≥k

⌊ n x ⌋ ≥ k ⇒ k x ≤ n \lfloor\dfrac{n}{x}\rfloor\ge k\Rightarrow kx\le n ⌊xn​⌋≥k⇒kx≤n

⇒ x ≤ ⌊ n k ⌋ \Rightarrow x\le \lfloor\dfrac{n}{k}\rfloor ⇒x≤⌊kn​⌋，即 x = n k x=\dfrac{n}{k} x=kn​

2.P4057 [Code+#1]晨跑

3个数的 l c m lcm lcm，利用 a b = l c m ∗ g c d ab=lcm*gcd ab=lcm∗gcd，然后就显然了。

3.P2118 [NOIP2014 普及组] 比例简化

l较小，暴力即可，貌似也没卡精度。

4.P2651 添加括号III

此题比较好，显然 a 1 a_1 a1​分子， a 2 a_2 a2​分母，而 a 3 . . . a n a_3...a_n a3​...an​位置可以任意。

1 / 2 / 3 / 4 = 1 × 3 2 × 4 1/2/3/4=\dfrac{1\times 3}{2\times 4} 1/2/3/4=2×41×3​

1 / ( ( 2 / 3 ) / 4 ) = 1 × 3 × 4 2 1/((2/3)/4)=\dfrac{1\times 3\times 4}{2} 1/((2/3)/4)=21×3×4​

1 / ( ( ( 2 / 3 ) / 4 ) / 5 ) = 1 × 3 × 4 × 5 2 1/(((2/3)/4)/5)=\dfrac{1\times 3\times4\times5}{2} 1/(((2/3)/4)/5)=21×3×4×5​

因为要化为整数，所以贪心地都给分子好了，然后就用gcd特判了。

int t,a[N],n;
bool ck(int n){
	int g=a[2]/__gcd(a[1],a[2]);
	for(int i=3;i<=n;i++){
		g/=__gcd(g,a[i]);
		if(g==1) return 1;
	}
	return g==1;
}

P5436 【XR-2】缘分

结论题，取最大的两个连续数互质，特判 n = 1 n=1 n=1即可。