脚本宝典收集整理的这篇文章主要介绍了# 算法竞赛进阶指南--打卡--数学知识篇--0x30，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

算法竞赛进阶指南--打卡--数学知识篇--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})=1iff 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)，对于(xnmid varphi(n))。

则(xnmid varphi(n)iffvarphi(n)=k*x+r,rin(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^2nmid 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游戏 （异或高斯消元，博弈论）

脚本宝典总结

以上是脚本宝典为你收集整理的# 算法竞赛进阶指南--打卡--数学知识篇--0x30全部内容，希望文章能够帮你解决# 算法竞赛进阶指南--打卡--数学知识篇--0x30所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。