时间限制$\text{: 2s / }$空间限制$\text{: 1024MB}$
分数:$400$ 分
题目描述 $\text{(Problem Statement)}$
$\text{Takahashi}$ 喜欢 $K$ 的倍数的数
在序列 $7, 77, 777, \ldots$ 这个序列中,第一个是 $K$ 的倍数的数是序列中的第几个?
如果该序列中不存在任何是 $K$ 的倍数的数,请输出 -1
约定 $\text{(Constraints)}$
- $1 \leq K \leq 10 ^ 6$
- $K$ 是一个整数
输入 $\text{(Input)}$
输入按如下形式的标准输入给出
K
输出 $\text{(Output)}$
输出一个整数,表示序列中第一个是 $K$ 的倍数的数的位置
输入样例1 $\text{(Sample Input 1)}$
101
输出样例1 $\text{(Sample Output 1)}$
2
输入样例2 $\text{(Sample Input 2)}$
-1
输出样例2 $\text{(Sample Output 2)}$
999983
输入样例3 $\text{(Sample Input 3)}$
999982
输出样例3 $\text{(Sample Output 3)}$
我太菜了,写题都不看数据范围。。后来才知道能 $O(K)$ 爆过去
看到这题,就以为数据范围是 $2 \times 10 ^ 9$,然后调半天 $O(\sqrt K \log K)$ 的程序,还 $\color{red}{WA}$ 了一次。。
这里给出两种解题方法与代码
算法1
(暴力枚举) $O(K)$
推式子题
首先 $7, 77, 777, \ldots$ 这种“字符串”数字不是很好处理,要先把它转化为一般的式子
考虑该序列第 $i$ 项,即
$\overbrace{77 \ldots 7} ^ \text{i 个}$
将其写成一堆数的和的形式,得到
$7 + 70 + \ldots + 7 \times 10 ^ {i - 1} = \sum _ {i = 0} ^ {n - 1} 7 \times 10 ^ i$
(抽象思维能力不好的同学,可以看等式左边这一项)
将因数 $7$ 提出,得到
$7 (1 + 10 + \ldots + 10 ^ {i - 1}) = 7 \times \sum _ {i = 0} ^ {n - 1} 10 ^ i$
根据等比数列求和公式{:target=”_blank”},得到
$7 \times {\large \frac {10 ^ i - 1} {10 - 1}} = {\large \frac 7 9} (10 ^ i - 1)$
也就是说,我们要找到一个最小的 $i$,使得 $K | {\large \frac 7 9} (10 ^ i - 1)$
也就是 $9 K | 7 (10 ^ i - 1)$
设 $d = \gcd(9 K, 7)$
$\because \gcd(9, 7) = 1$
$\therefore d = \gcd(K, 7)$
原式两边可以同时除以 $d$,得到
$9 \times {\large \frac K d | \frac 7 d} (10 ^ i - 1)$(由于 $d$ 是左边和 $7$ 的最大公因数,所以一定可以整除)
右边的 $\large \frac 7 d$ 和左边一定没有公因数(否则不符合 $\small d = \gcd(9 K, 7)$),所以可以将其去掉,得到
$9 \times {\large \frac K d} | (10 ^ i - 1)$
左边是一个常数,设 $c = 9 \times {\large \frac K d}$,那么我们要求的就是
$10 ^ i - 1 \equiv 0 \quad (\text{mod}\ c)$
$\Rightarrow 10 ^ i \equiv 1 \quad (\text{mod}\ c)$
这个就是我们平常常见的形式了
那么根据欧拉定理{:target=”_blank”},当 $10 ^ i$ 与 $c$ 互质时,有
$10 ^ {\varphi(c)} \equiv 1 \quad (\text{mod}\ c)$
所以 $\varphi(c)$ 是一个答案,但是,它并不一定是我们所求的最小答案
我们需要从 $1 \sim \varphi(c)$ 枚举一遍,同时维护数列中第 $i$ 个数 $\text{mod}\ c$ 的结果
如果某个数 $\text{mod}\ c$ 为 $0$,则直接输出该数,否则输出-1
(当然也可以特判答案为 -1
的情况)
时间复杂度
这里的代码并不是只枚举到 $\varphi(c)$ 的(我偷个懒,给个比较简短的代码)而是直接暴力枚举到 $9 K$ 的,
由于,当 $10 ^ i$ 与 $c$ 互质时,$10 ^ {\varphi(c)} \equiv 1 \quad (\text{mod}\ c)$,所以我们的答案最多会是 $\varphi(c)$
又因为 $\varphi(c) < c = 9 {\large \frac K {\gcd(K, 7)}} < 9 K$,所以我们在枚举到 $9K$ 之前,一定会找到一个答案(否则无解)
循环从 $1 \sim 9 K$ 枚举一遍,时间复杂度为 $O(K)$
C ++ 代码
#include <cstdio>
int main()
{
int k;
scanf("%d", &k);
// i 为当前枚举到了序列中第几个数,p 为当前枚举的数 mod k 的结果
for (int i = 1, p = 7; i < 9 * k; i ++ , p = (10 * p + 7) % k)
if (p % k == 0) // 注意这里不能直接写 !p,因为有可能 k == 7,那么第一次就会不输出
{ // 如果特判了 k == 7 的情况,或者是一开始让 p = 7 % k,那么这里可以直接写 !p
printf("%d\n", i);
return 0;
}
puts("-1"); // 无解输出 -1
return 0;
}
算法2(算法1优化)
(不那么暴力的枚举) $O(\sqrt K \log K)$
这里先给出结论,再证明(下面所有字母含义与 算法1
中相同)
- 结论:如果存在答案,设答案为 $ans$,则 $ans|\varphi(c)$
- 证明:反证法,假设 $ans \nmid \varphi(c)$
那么就可以令 $\varphi(c) = k \times ans + r$,其中 $0 < r < ans$
由于 $ans$ 是一个合法解,所以 $10 ^ {ans} \equiv 1 \quad (\text{mod}\ c)$
两边同时 $k$ 次方,得 $10 ^ {k \times ans} \equiv 1 \quad (\text{mod}\ c)$
由于 $\varphi(c)$ 是一个合法解,所以 $10 ^ {\varphi(c)} \equiv 1 \quad (\text{mod}\ c)$
$\Rightarrow 10 ^ {k \times ans + r} \equiv 1 \quad (\text{mod}\ c)$
又因为 $10 ^ {k \times ans} \equiv 1 \quad (\text{mod}\ c)$,所以可以两边同时 $\div 10 ^ {k \times ans}$
得到 $10 ^ r \equiv 1 \quad (\text{mod}\ c)$,所以 $r$ 也是一个合法解
由于 $0 < r < ans$,不满足 $ans$ 是最小的合法解
所以假设不成立,原命题证毕
所以,我们只需要先求出 $\varphi(c)$,然后再枚举 $\varphi(c)$ 的所有约数,判断每个约数是否为合法解即可
时间复杂度
首先 $\varphi(c)$ 是可以 $O(\sqrt c)$ 求出来的,板子题在这里{:target=”_blank”}
然后枚举 $\varphi(c)$ 的所有约数,时间复杂度为 $O(\sqrt {\varphi(c)})$ 的,板子题在这里{:target=”_blank”}
判断每个约数是否合法(即判断 $10 ^ i \text{ mod } c$ 是否为 $1$),时间复杂度为 $O(\log \sqrt {\varphi(c)})$,需要用快速幂,板子题在这里{:target=”_blank”}
那么总的时间复杂度即为 $O(\sqrt c + \sqrt {\varphi(c)} \log \sqrt {\varphi(c)})$
因为最坏情况下 $\varphi(c)$ 和 $c$ 是一个级别的,所以时间复杂度可化简为 $O(\sqrt c \log \sqrt c)$
上面已经证明了 $c < 9K$,也就是说,$c$ 和 $K$ 是一个级别的
所以时间复杂度可化简为 $O(\sqrt K \log \sqrt K) = O(\sqrt K \log (K ^ \frac 1 2)) = O(\frac 1 2 \sqrt K \log K) = O(\sqrt K \log K)$
C++ 代码
#include <cstdio>
const int INF=0x3fffffff;
// n 即为 K
int n;
int min(int a, int b)
{
return a < b ? a : b;
}
// 欧拉函数的板子,返回 phi(x)
int get_phi(int x)
{
int res = x;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
res -= res / i;
while (x % i == 0) x /= i;
}
if (x > 1) res -= res / x;
return res;
}
// 快速幂板子,求 10 的 k 次方模 mod 的结果
int qmi(int k, int mod)
{
int res = 1, a = 10;
while (k)
{
// mod 即 c,最大是 n * 9 = 9e6,乘法就可能会爆 int,要转 long long
if (k & 1) res = res * 1ll * a % mod;
a = a * 1ll * a % mod;
k >>= 1;
}
return res;
}
int main()
{
scanf("%d", &n);
// 让 n 变成 c
if (n % 7 == 0) n /= 7; // 由于 7 是质数,所以这里不用再求一遍最大公约数,直接判断是否有因子 7 即可
n *= 9;
// phi 存 phi(c) 的值。res 记录答案,初始化为正无穷
int phi = get_phi(n), res = INF;
for (int i = 1; i <= phi / i; i ++ )
if (phi % i == 0) // 如果 i 是 phi 的因子,那么分别判断 i 和 phi / i 是否是合法解,如果是,则更新答案
if (qmi(i, n) == 1) res = min(res, i); // 由于 i <= phi / i,所以如果 i 是合法解,就不用再判断 phi / i 了
else if (qmi(phi / i, n) == 1) res = min(res, phi / i);
printf("%d\n", res == INF ? -1 : res); // 如果 res == INF,说明无解,输出 -1,否则输出 res
return 0;
}
$$ $$