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

2022/1/7 9:03:39

本文主要是介绍# 算法竞赛进阶指南--打卡--数学知识篇--0x30,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

①:可见的点(欧拉函数,暴力)

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

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

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

3090_1.png

编写一个程序,计算给定整数 \(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游戏 (异或高斯消元,博弈论)



这篇关于# 算法竞赛进阶指南--打卡--数学知识篇--0x30的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程