算法竞赛进阶指南--打卡--数学知识篇--0x30

①：可见的点（欧拉函数，暴力）

在一个平面直角坐标系的第一象限内，如果一个点$ (x,y)$ 与原点 \((0,0)\)的连线中没有通过其他任何点，则称该点在原点处是可见的。

例如，点 \((4,2)\) 就是不可见的，因为它与原点的连线会通过点$ (2,1)$。

部分可见点与原点的连线如下图所示：

编写一个程序，计算给定整数 \(N\) 的情况下，满足 \(0≤x，y≤N\) 的可见点 \((x，y)\)的数量（可见点不包括原点）。

我们考虑一个东西，什么点不可能被遇见。

如果点\((x,y)\)可见，则\((k*x,k*y)\)一定不可见。

也就是，如果\(\gcd(x,y)!=1\)则一定不可见，也就是\(x,y\)不互质一定不可见。

那么显然，互质一定可见。

因此题目就是求欧拉函数的前缀和。

因为\((1,1)\)可见，但是欧拉函数的计算中未被加入，因此最后给总量加上一即可。

②： 最幸运的数字 （推公式，数论）

\(8\) 是中国的幸运数字，如果一个数字的每一位都由 \(8\) 构成则该数字被称作是幸运数字。

现在给定一个正整数 \(L\)，请问至少多少个 \(8\) 连在一起组成的正整数（即最小幸运数字）是 \(L\) 的倍数。

由题，有条件\(L|8*\frac{(10^x-1)}9\)，。求\(x\)的最小正整数解

我们可以对上式进行一些变形：

\(L|8*\frac{(10^x-1)}9 \iff 9*L|8*(10^x-1)\)

我们记有\(d=\gcd(8,L)\)

显然有\(9*L|8*(10^x-1) \iff \frac{9*L}{d}|\frac{8*(10^x-1)}{d}\)

由于\(\gcd(\frac{8}{d},9)=1\) and \(\gcd(\frac{8}{d},\frac{L}{d})=1\)

因此\(\frac{9*L}{d}\)与\(\frac{8}{d}\)互质。因此\(\frac{9*L}{d}|\frac{8*(10^x-1)}{d} \iff \frac{9*L}{d}|10^x-1\)

上式等价于\(10^x \equiv 1 \mod \frac{9*L}{d}\)，求\(x\)的最小正整数解。

当同余方程\(a*x \equiv c \mod b\)有解时，\(\gcd(a,b)|c\)为充分必要条件。

由于本题较为特殊，发现如果有解则\(\gcd(10,\frac{9*L}{d})=1\)。

证明：

显然\(\gcd(10,9)=1\)，并且$\gcd(\frac{8}{d},\frac{L}{d})=1\iff \gcd(8,\frac{L}{d})=1 \(，并且\)\gcd(8,10)=2$。

综合上述式子，\(\gcd(8,10,\frac{L}{d})=1\)，故\(\gcd(10,\frac{L}{d})=1\)。

故必然有\(\gcd(10,\frac{9*L}{d})=1\)。

因此很容易，我们利用欧拉定理即可解出一个解\(x_{0}\)。但是此解不一定为最小解。

可以推导出，最小解一定为\(x_{0}\)的一个因子。

证明：

反证法：

对于同余方程\(a^x \equiv 1 \mod n\)，并且\(\gcd(a,n)=1\)。如果有解\(x\)，对于\(x\nmid \varphi(n)\)。

则\(x\nmid \varphi(n)\iff\varphi(n)=k*x+r,r\in(0,x)\)。

由欧拉定理，有\(a^{\varphi(n)} \equiv 1 \mod n\)

故有\(a^{k*x+r} \equiv 1 \mod n\)。由于\(x\)为同余方程的一个解，则\(a^x \equiv 1 \mod n\)。

\(a^{x} \equiv 1 \mod n \iff a^{k*x} \equiv 1 \mod n\)

所以有，\(a^{r} \equiv 1 \mod n\)，由于\(r<x\)，且解\(r\)符合要求，故\(r\)为较小解，直至\(r=0\)时，\(x\)才为最小解。故最小解为当前解的某个因子。

因此我们从小到大枚举\(x_0\)的因子，第一个符合答案即为最小解。

③： 异或运算 （线性基，异或高斯消元）

说实话，感觉这道题比之前的开关问题的异或方程更形象

给定你由 \(N\) 个整数构成的整数序列，你可以从中选取一些（至少一个）进行异或（\(XOR\)）运算，从而得到很多不同的结果。

请问，所有能得到的不同的结果中第 $k $小的结果是多少。

\(1≤N,Q≤10000, 1≤k_i≤10^{18}\)

由于“异或”符合交换律与结合律，故可以按照高斯消元法逐步消元求解。

关键大概就是上面的这句话。

我们将个整数按顺序从大到小排序。

\(N\)个整数，我们将其各个二进制位提出，作为未知数，但是没有发现常数项，观察题目，发现无所谓。

我们对\(N\)条方程高斯消元，对多只会剩下\(64\)条方程组。

由于高斯消元进行线性变换，其向量组合张成的空间无变化。也就是我们可以使用\(64\)条方程组代表\(N\)条方程组能做到事。（我事线代垃圾，只能这样解释了）

我们在上面的操作过后，消元得到整数表示的方程组一定严格递增。

我们这里只要特判一个点：

方程是否有零向量

显然，对于任意零向量\(zero\)异或任何向量\(any\)都为\(any\)。

对于每一个询问第\(k\)小。

不存在零向量时，显然我们可以按照\(k\)二进制从低到高位数上为是否\(1\)从而从小到大对整数进行异或。

为什么呢？对于消元后的整数\(A[i]>A[i+1]\)，高斯消元，保证存在唯一解的未知数只出现一个为\(1\)的系数，否则均为\(0\)。

因此系数为\(1\)越高位的二进制位数越靠前出现，保证我们一堆数越小，就尽可能保证越高为不会出现，因此我们尽可能选小的数。由于每一个数最多选一次，因此\(k\)的二进制正形式好符合性质。

但是题目要求不同结果

故存在零向量时，大小不断仅在最末端添加零元素，其他时候与零元素无关。也就是我们对\(k\)取二进制时事先减一即可。

④： 最大公约数 （推公式，线性筛递推欧拉函数）

给定整数 \(N\)，求 \(1≤x,y≤N\)且 \(GCD(x,y)\) 为素数的数对 \((x,y)\) 有多少对。

\(GCD(x,y)\))即求 \(x，y\) 的最大公约数。

我们要求\(GCD(x,y)\)=质数。显然，对于任意一个数\(x\)，都可以表示成\(1*x\)。

我们假设存在数对\((x,y),x<y\)。若\(\gcd(x,y)=1\)则\(\gcd(k*x,k*y)=k\)。

故我们只要求存在多少互质的数对即可，同上方的题目"可见的点"。

但是数据范围为\(1e7\)，暴力算欧拉函数显然不可取。

因此我们由欧拉函数的推论

欧拉函数的推论:
①若\(p\)为质数，且\(p|n\)，\(p^2|n\)，则\(\varphi(n)=\varphi(n/p)*p\)

②若\(p\)为质数，且\(p|n\)，\(p^2\nmid n\)，则\(\varphi(n)=\varphi(n/p)*(p-1)\)

故采用线性筛的思想，可以在\(O(n)\)的时间内求出\([1,n]\)的所有欧拉函数。

⑤： 龙哥的问题 （欧拉函数，暴力，推公式）

龙哥现在有一道题，要考考大家。

给定一个整数 \(N\)，请你求出 \(∑_{1≤i≤N}\gcd(i，N)\)的值。

如果存在数\(x=\gcd(a,b)\)，则\(x\)一定属于\(a,b\)的因子。

因此对于上式\(∑_{1≤i≤N}\gcd(i，N)\)，我们只要按照\(N\)的因子\(d_{i}\)枚举即可。

假设\(\gcd(i,N)=d_i\)，则\(i=k_1*d_i,N=k_2*d_i\)。

显然，\(\gcd(\frac{i}{d_i},\frac{N}{d_i})=1\)。

因此所有\(\gcd(i,N)=d_i\)的情况共有\(\varphi(\frac{N}{d_i})\)种。

因此可以推出公式\(res=∑_{i=1}^{k}\varphi(\frac{N}{d_i})*d_i\)。

⑥： 矩阵幂求和 （矩阵乘法，分治）

⑦： Hankson的趣味题 （乱搞，推公式，数论）

⑧： 剪纸游戏 （博弈论，SG函数）

⑨： 新NIM游戏 （异或高斯消元，博弈论）