UVA 数学题选做

UVA12716 GCD等于XOR GCD XOR

考虑枚举 \(c=\gcd(a,b)\)，因为 \(\gcd(a,b)|a\land \gcd(a,b)|b\)，所以再枚举 \(a\)，且 \(a\) 是 \(c\) 的倍数。因为 \(\gcd(a,b)=a \operatorname{xor} b\)，所以 \(b=c\operatorname{xor} a\)，然后再验证 \(\gcd(a,b)\) 是否等于 \(c\) 即可。

但实际上我们可以知道 \(\gcd(a,b)\) 一定等于 \(a-b\)。不妨令 \(a>b\)（因为 \(a=b\) 的情况一定不合法），因为 \(a-b\le a \operatorname{xor} b \le a+b\) 且 \(\gcd(a,b)=\gcd(b,a-b)\le a-b\)，结合两个式子就可以得到 \(\gcd(a,b)=a-b\)。

于是枚举 \(c,a\)，算出 \(b=a-c\) 并验证 \(a\operatorname{xor} b\) 是否等于 \(a-b\) 即可。

因为数据组数比较多，所以考虑算出某个特定的 \(a\) 的答案，并进行一次前缀和，时间复杂度为 \(O(n\log n+T)\)。

UVA11440 帮帮 Tomisu Help Tomisu

一个数 \(x\) 的所有大于 \(1\) 的因子都大于 \(M\iff x \perp M!\)。

因为 \(N\ge M\) 所以 \(M!|N!\)，同时我们知道 \(x\perp M!\iff (x\bmod M!) \perp M!\)，于是答案就是 \(\varphi(M!)\frac{N!}{M!}\)。

考虑怎么求 \(\varphi(M!)\)：我们知道 \(\varphi(x)=x(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})\dots(1-\dfrac{1}{p_k})\)，当 \(M\) 是质数的时候，它会贡献 \((M-1)\)，即 \(\varphi(M!)=\varphi((M-1)!)\times (M-1)\)；当 \(M\) 不是质数的时候，它会贡献 \(M\)。递推即可。

UVA1642 魔法GCD Magical GCD

考虑枚举这个区间的右端点，并维护所有最优的左端点。

可以发现，\(\gcd(a_l\dots a_r)|\gcd(a_{l+1}\dots a_r)\)，于是在固定右端点的情况下，\(\gcd\) 值不同的位置只有 \(\log n\) 个。暴力维护每个 \(\gcd\) 值对应的最靠右的左端点，将右端点向右移动的过程中进行修改即可。时间复杂度 \(O(n \log^2 n)\)。

顺便讲讲我的屑做法：用 sparse table 记录区间 \(\gcd\)，枚举右端点以及 \(\gcd\) 并二分。但这复杂度巨高，大概是 \(O(\sum d(a_i)\log ^2n)\) 的。

#include 
#include 
#include 
#include