P2568 GCD
给定正整数 \(n\)，求正整数数对 \((x,y)\) 的个数，该数对满足 \(x\leq n,y\leq n\) 且 \(\gcd(x,y)\) 是质数。
首先我们可以枚举质数 \(p\)，求出 \(\gcd(x,y)=p\) 的数对个数然后对每一个质数求和即可。所以考虑如何求这个子问题。
给定质数 \(p\)，求满足 \(x\leq n,y\leq n\) 且 \(\gcd(x,y)=p\) 的数对 \((x,y)\) 个数。
根据 \(\gcd\) 的性质有 \(\gcd(x,y)=p\Rightarrow \gcd(\frac{x}{p},\frac{y}{p})=1\)，满足 \(\frac{x}{p},\frac{y}{p}\leq\frac{n}{p}\)，即求出小于 \(\frac{n}{p}\) 的互质数对个数。
我们设 \(g(x)\) 表示小于等于 \(x\) 的互质数对个数，用 \(\mathbb{P}\) 表示质数集，则原题目答案为：
\[\text{Answer}=\sum_{p\in P \wedge p\leq n} g\left(\left\lfloor\frac{n}{p}\right\rfloor\right). \]所以考虑怎么求 \(g(x)\)。
注意到是 互质 数对，可以考虑欧拉函数。我们有：
\[g(n)=-1+2\times\sum_{i=1}^{n}\varphi(i). \]解释：\(\varphi(i)\) 表示小于等于 \(i\) 的与它互质的数的个数，则求和后就是 \(g(n)\)，但注意数对 \((x,y)\neq(y,x)\)，所以要乘以 \(2\)，但是减去 \(1\) 是由于 \((1,1)=(1,1)\)。
所以线性求欧拉函数之后前缀和求 \(g\) 函数然后遍历一遍质数求和即可。时间复杂度为 \(O(n+\pi(n))\)。
P1445 [Violet]樱花
给定 \(n\)，求以下方程正整数解个数。
\[\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}. \]
注意到由于 \(x,y\) 为正，则 \(\frac{1}{x}\) 与 \(\frac{1}{y}\) 都小于 \(\frac{1}{n!}\)，所以 \(x\) 和 \(y\) 都大于 \(n!\)。
设 \(y=n!+k\)，其中 \(k\in \mathbb{Z^+}\)。于是有：
\[\begin{aligned} \frac{1}{x}+\frac{1}{n!+k}&=\frac{1}{n!}.\\ (n!+k)\cdot n! + x\cdot n!&=x\cdot(n!+k).\\ (n!)^2+k\cdot n! &= x\cdot k.\\ x&=\frac{(n!)^2}{k}+n!. \end{aligned} \]由于 \(x\in \mathbb{Z^+}\)，而 \(n!\in\mathbb{Z^+}\)，于是 \(\frac{(n!)^2}{k}\in\mathbb{Z^+}\)，即 \(k\) 是 \((n!)^2\) 的因数。
所以枚举 \(1\) 至 \(n\)，暴力计算分解后的质数个数然后加一相乘即可。
P3927 SAC E#1 - 一道中档题 Factorial
给定正整数 \(n,K\)，满足 \(1\leq n\leq 10^{12},2\leq K\leq 10^{12}\)，求 \(n!\) 在 \(K\) 进制下末尾 \(0\) 的个数。
显然：
若存在正整数 \(x\) 满足 \(K^x\ |\ n\) 则 \(n\) 在 \(K\) 进制下的末尾至少有 \(x\) 个零。
所以题目可转化为求最大的 \(x\) 使 \(K^x\) 整除 \(n!\)。考虑一个朴素解法，暴力分解 \(n!\) 以及 \(K\)，然后考虑 \(n!\) 的因子包含几个 \(K\) 的因子，然后即可注意到，如果这个因子不是 \(K\) 的因数，则不用考虑。
所以朴素方法如下：
分解 \(K\) 得到 \(K=p_1^{k_1}\cdot p_2^{k_2}\cdots p_m^{k_m}\)，其中 \(p_i\) 都是质数，我们拿每个质数去除 \(P=n!\)，记 \(q_i\) 表示 \(P\) 能被 \(p_i\) 整除的次数，则答案为：
\[\text{Answer}=\min_{i=1}^m \left\lfloor\frac{q_i}{k_i}\right\rfloor. \]自然语言描述就是对于每个 \(p_i^{k_i}\) 求出 \(P\) 最多能被他们的几次方整除，最后取 \(\min\)。
时间复杂度分析：质因数分解 \(K\) 时间复杂度为 \(O(\sqrt{K})\)，易证得 \(m\leq \log_2 K\)，整除的总次数 \(\sum q_i \leq \log_2 n!\)，则总时间复杂度为 \(O(\sqrt{K}+\log_2 K+\log_2 n!)\)。
会发现时间复杂度的瓶颈在于求出每个因子在 \(n!\) 中有几次，即 \(O(\log_2 n!)\) 这部分。考虑怎么加速处理出 \(q_i\)。
对每个 \(p_i\) 单独考虑，分开看 \(n!=1\times 2\times 3\times\cdots\times n\)，其中包含大于等于 \(1\) 次的 \(p_i\) 因子的数的个数为 \(\left\lfloor\frac{n}{p_i}\right\rfloor\)，所以 \(q_i\leftarrow\left\lfloor\frac{n}{p_i}\right\rfloor\)。而其中包含大于等于 \(2\) 次 \(p_i\) 因子的数的个数则为 \(\left\lfloor\frac{n}{p_i^2}\right\rfloor\)，所以 \(q_i\leftarrow q_i + \left\lfloor\frac{n}{p_i^2}\right\rfloor\)，这里只加一次是因为第一次被前一种情况包含了。同理可处理包含大于等于 \(j\) 次 \(p_i\) 因子的数的个数。
所以计算 \(q_i\) 我们有以下的代码：
for (int i = 1; i <= m; i ++) {
LL tmp = n; q[i] = 0;
while (tmp > 0) {
q[i] += tmp / p[i];
tmp /= p[i];
}
}
然后即可重复朴素算法的操作求出答案。
时间复杂度分析：由于 \(n,K\) 同阶，以下都用 \(n\) 表示。与朴素算法相比仅相差计算 \(q_i\) 的操作。对于每个因子而言，记 \(a_i\) 表示 \(n\) 至多能被她除几次才为 \(0\)，则显然 \(a_i\leq \log_{p_i} n\leq \log_2 n\)，而因子一共小于 \(\log_2 n\) 个，则处理 \(q\) 数组的时间复杂度仅为 \(O(\log_2^2n)\)，所以总时间复杂度为 \(O(\sqrt{n}+\log_2 n+\log_2^2n)\)，即 \(O(\sqrt{n}+\log^2_2 n)\)。
P10496 The Luckiest Number
给定一个正整数 \(k\)，求最小的正整数 \(x\) 满足 \(k\) 能整除 \(x\) 个 \(8\) 组合起来的正整数。
易发现 \(x\) 个 \(8\) 连起来的数为 \(8\times111\cdots111=8\times\frac{10^x-1}{9}\)。所以题目就是要求出一个最小的正整数 \(x\) 满足 \(k \ | \ 8\times \frac{10^x-1}{9}。\)
两边同时乘以 \(9\) 得到 \(9k \ | \ 8\times (10^x-1)\)。记 \(d\) 表示 \(\gcd(k,8)\) 则有：
\[\frac{9k}{d} \ | \ 10^x-1. \]所以有：
\[\begin{aligned} 10^x-1&\equiv 0\quad(\bmod\ \frac{9k}{d}),\\ 10^x&\equiv1\quad (\bmod\ \frac{9k}{d}). \end{aligned} \]引理：当 \(a,n\) 互质时 \(a^x\equiv1\ (\bmod\ n)\) 的最小正整数解 \(x_0\) 整除 \(\varphi(n)\)。
证明：使用反证法。若 \(x_0\) 不能整除 \(\varphi(n)\)，则存在正整数 \(p,q\) 满足 \(\varphi(n)=px_0+q,1\leq q< x_0\)。由题设有 \(a^{x_0}\equiv 1\ (\bmod\ n)\)，所以 \(a^{px_0}\equiv 1\ (\bmod\ n)\)，而由欧拉定理可得 \(a^{\varphi(a)}\equiv 1\ (\bmod\ n)\)，两式相除得到 \(a^{\varphi(a)-px_0}\equiv 1\ (\bmod\ n)\)，即 \(a^q\equiv 1\ (\bmod\ n)\)，而 \(q<x_0\)，与题设 \(x_0\) 的最小性不符。所以原命题为真命题。证毕。
所以本题所求 \(x\) 一定是 \(\varphi(\frac{9k}{d})\) 的因数，枚举即可。
标签：frac,log,质数,个数,leq,论题,正整数,有趣,Updating From： https://www.cnblogs.com/LaDeX-Blog/p/18475497/Intersting-Problem-of-Number-Theory