314 lines
10 KiB
Markdown
314 lines
10 KiB
Markdown
##[$AcWing$ $202$. 最幸运的数字](https://www.acwing.com/problem/content/description/204/)
|
||
|
||
### 一、题目描述
|
||
$8$ 是中国的幸运数字，如果一个数字的每一位都由$8$构成则该数字被称作是幸运数字。
|
||
|
||
现在给定一个正整数 $L$，请问 **至少多少个$8$连在一起组成的正整数**（即最小幸运数字）是$L$的倍数。
|
||
|
||
**输入格式**
|
||
输入包含多组测试用例。
|
||
|
||
每组测试用例占一行，包含一个整数 $L$。
|
||
|
||
当输入用例 $L=0$ 时，表示输入终止，该用例无需处理。
|
||
|
||
**输出格式**
|
||
每组测试用例输出结果占一行。
|
||
|
||
结果为 `Case i:`+一个整数 $N$，$N$ 代表满足条件的最小幸运数字的位数。
|
||
|
||
如果满足条件的幸运数字不存在，则 $N=0$。
|
||
|
||
**数据范围**
|
||
$1≤L≤2×10^9$
|
||
|
||
**输入样例**
|
||
```cpp {.line-numbers}
|
||
8
|
||
11
|
||
16
|
||
0
|
||
```
|
||
**输出样例**
|
||
```cpp {.line-numbers}
|
||
Case 1: 1
|
||
Case 2: 2
|
||
Case 3: 0
|
||
```
|
||
|
||
### 二、前导知识
|
||
用到了 $6$个前导知识点：
|
||
|
||
**1. 由 $x$ 个 $y$ 组成的数的公式是$\large \displaystyle y \times \frac{10^x-1}{9}$,比如 $88888888$这种数。**
|
||
$\large \displaystyle \underbrace{8...8}_{x}=8 \times \underbrace{1...1}_{x}=8 \times \frac{\underbrace{9...9}_{x}}{9}=8 \times \frac{10^x-1}{9}$
|
||
|
||
**2. 欧拉定理**
|
||
|
||
若正整数$a, n$互质，则 $$\large a^{φ(n)}≡1(mod \ n)$$
|
||
|
||
其中$\phi(n)$指欧拉函数值,$(1\sim n)$与$n$互质的数。
|
||
|
||
**3. 欧拉定理推论**
|
||
若正整数$a,n$互质，则满足$a^x \equiv 1 \ (mod \ n)$的 **最小正整数解** $x_0$是$\phi(n)$的约数。
|
||
|
||
**反证法**：假设该最小正整数 $x$不是 $φ(c)$ 的约数
|
||
则 $φ(c)=qx+r(0<r<x)$，
|
||
又
|
||
|
||
$$
|
||
\large \left\{\begin{matrix}
|
||
& 10^x \equiv 1 \ (mod\ c) \Rightarrow 10^{qx} \equiv 1 (mod \ c) \ ①\\
|
||
& 10^{φ(c)} \equiv 1 \ (mod\ c) \Rightarrow 10^{qx+r} \equiv 1 (mod \ c) \ ②
|
||
\end{matrix}\right.
|
||
$$
|
||
|
||
|
||
由 ② 式除以 ① 式得 $10^r≡1 \ (mod \ c)(0<r<x)$
|
||
故存在比 $x$ 更小的正整数满足该式子，矛盾了
|
||
因此得证
|
||
|
||
**4. 快速幂**
|
||
```cpp {.line-numbers}
|
||
int qmi(int a, int b, int p) {
|
||
int res = 1;
|
||
while (b) {
|
||
if (b & 1) res = res * a % p;
|
||
b >>= 1;
|
||
a = a * a % p;
|
||
}
|
||
return res;
|
||
}
|
||
```
|
||
**5. 快速幂+快速乘**
|
||
当模数$>1e9$的时候，在相乘的时候爆$long$ $long$了。
|
||
|
||
```cpp {.line-numbers}
|
||
//快速乘
|
||
//时间复杂度：logn,乘法本来是O(1),这么干成了O(logN)了。
|
||
//优点：可以防止在LL*LL % MOD 过程中爆掉LL，可以将乘法分解成多步加法，在加的过程中不断取模。
|
||
int qmul(int a, int b, int mod) {
|
||
LL res = 0;
|
||
while (b) {
|
||
if (b & 1) res = (res + a) % mod;
|
||
a = (a + a) % mod;
|
||
b >>= 1;
|
||
}
|
||
return res;
|
||
}
|
||
|
||
//快速幂+快速乘
|
||
int qmi(int a, int b, int mod) {
|
||
int res = 1;
|
||
while (b) {
|
||
if (b & 1) res = qmul(res, a, mod); //调用龟速乘,原因是本题的数据范围是2*1e9,直接乘会爆掉LL，需要一路乘来一路取模
|
||
a = ksc(a, a, mod);
|
||
b >>= 1;
|
||
}
|
||
return res;
|
||
}
|
||
```
|
||
|
||
**6. $\_\_int128$配合快速幂**
|
||
```cpp {.line-numbers}
|
||
typedef __int128 LLL;
|
||
|
||
//快速幂+ LLL
|
||
int ksm(int a, int b, int mod) {
|
||
int res = 1;
|
||
while (b) {
|
||
if (b & 1) res = (LLL)res * a % mod;
|
||
a = (LLL)a * a % mod;
|
||
b >>= 1;
|
||
}
|
||
return res;
|
||
}
|
||
|
||
```
|
||
|
||
|
||
### 三、本题思路
|
||
|
||
题目实际上要我们求一个最小的正整数 $x$，满足 $\large \displaystyle L|8*\frac{10^x-1}{9}$
|
||
|
||
转化条件：
|
||
$$\large \displaystyle \Leftrightarrow 9*L | 8 * (10^x-1)$$
|
||
|
||
令$\large \displaystyle d=gcd(L,8)$,约分:
|
||
$$\large \displaystyle \Leftrightarrow \frac{9*L}{d} | 10^x-1 \ \ \ \ ①$$
|
||
$$\large \displaystyle \Leftrightarrow 10^x-1 \equiv 0 \ (mod \ \frac{9*L}{d})$$
|
||
$$\large \displaystyle \Leftrightarrow 10^x \equiv 1 \ (mod \ \frac{9*L}{d})$$
|
||
|
||
设$\large \displaystyle p=\frac{9*L}{d}$
|
||
|
||
即:
|
||
$$\large \displaystyle \Leftrightarrow 10^x \equiv 1 \ (mod \ p)$$
|
||
|
||
最终变成 <font color='red' size=4><b>求解满足 $\large \displaystyle 10^x≡1(mod \ p)$ 的最小正整数 $x$</b></font>
|
||
|
||
> **注释**
|
||
> $d$既然是两个数的最大公约数，那么两个数都除以$d$后，得到的两个新数，必然互质 (最大公约数的定义)
|
||
> 即：$\large \displaystyle \frac{9*L}{d}$与$\large \displaystyle \frac{8}{d}$是互质的,而$\large \displaystyle 10^x-1$还想是$\large \displaystyle \frac{9*L}{d}$的整数倍
|
||
> 所以 $\large \displaystyle \frac{9*L}{d}$一定是$\large \displaystyle 10^x-1$的因数，所以$\large \displaystyle : \frac{9*L}{d} | 10^x-1$
|
||
|
||
### 四、欧拉定理+推论
|
||
欧拉定理: $\large \displaystyle a^{φ(n)}≡1(mod \ n)$(其中$\large \displaystyle gcd(a,n)=1$)
|
||
|
||
这里的形式有点像欧拉定理，$\large a^{\phi(p)}\equiv 1 (mod \ p)$但是欧拉定理只是说$\large φ(p)$是一个解，但不能保证 $\large φ(p)$ 是满足等式的最小正整数!
|
||
|
||
由于我们学习过前导知识，知道如果想求最小正整数解$\large x_0$，其实需要满足$\large x_0|\phi(n)$,我们只需要枚举每个$\large \phi(n)$的约数，找出满足条件的最小正整数$\large x_0$即可。
|
||
|
||
|
||
### 五、实现代码(快速幂+快速乘)
|
||
```cpp {.line-numbers}
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
#define int long long
|
||
#define endl "\n"
|
||
|
||
// 最大公约数
|
||
int gcd(int a, int b) {
|
||
if (b == 0) return a;
|
||
return b ? a : gcd(b, a % b);
|
||
}
|
||
|
||
// 快速乘
|
||
int ksc(int a, int b, int mod) {
|
||
int res = 0;
|
||
while (b) {
|
||
if (b & 1) res = (res + a) % mod;
|
||
a = (a + a) % mod;
|
||
b >>= 1;
|
||
}
|
||
return res;
|
||
}
|
||
|
||
// 快速幂+快速乘
|
||
int ksm(int a, int b, int mod) {
|
||
int res = 1;
|
||
while (b) {
|
||
if (b & 1) res = ksc(res, a, mod);
|
||
a = ksc(a, a, mod);
|
||
b >>= 1;
|
||
}
|
||
return res;
|
||
}
|
||
|
||
/**
|
||
* 功能：计算单个数字的欧拉函数值
|
||
* @param x
|
||
* @return
|
||
*/
|
||
int phi(int x) {
|
||
int res = x;
|
||
for (int i = 2; i <= x / i; i++)
|
||
if (x % i == 0) {
|
||
res = res / i * (i - 1);
|
||
while (x % i == 0) x /= i;
|
||
}
|
||
if (x > 1) res = res / x * (x - 1);
|
||
return res;
|
||
}
|
||
|
||
signed main() {
|
||
int T = 1; // 准备输出Case i
|
||
int L;
|
||
while (cin >> L, L) {
|
||
int d = gcd(L, 8); // L和8的最大公约数 gcd(8,L)
|
||
int mod = 9 * L / d; // 公式推导得到的mod
|
||
int p = phi(mod); // 单个数字mod的欧拉函数值φ(mod)
|
||
int res = LONG_LONG_MAX; // 预求最小先设最大
|
||
|
||
if (gcd(mod, 10) > 1) // 判断mod和10是否互质,不互质:方程无解，输出0
|
||
res = 0;
|
||
else {
|
||
for (int d = 1; d * d <= p; d++) // 枚举φ(p)的每个小约数,到sqrt(φ(p))
|
||
if (p % d == 0) { // 如果d是约数,那么其实我们一次发现了两个约数： d 和 phi/d
|
||
// 这里与原来的质因子分解有一点点不同，因为那个只要枚举小于sqrt(n)的，并且 n %d==0,
|
||
// 就一定是它的小质数因子，本题不是这个意思。
|
||
// 本题的目标是找出所有因子，注意，不是小因子。
|
||
// 因为，小因子不见得能是方程的解，大因子不见得不是方程的解！！
|
||
// 对于它们，都有机会成为答案，需要全部讨论到！然后PK最小值即可！
|
||
// 如果这个约数d，满足 10 ^ d ≡ 1 (mod p) ，那么它有机会成为答案
|
||
if (ksm(10, d, mod) == 1) res = min(res, d); // 小约数
|
||
// 如果这个约数phi/d，满足 10 ^ (phi/d) ≡ 1 (mod p) ，那么它有机会成为答案
|
||
if (ksm(10, p / d, mod) == 1) res = min(res, p / d); // 大约数
|
||
}
|
||
}
|
||
// 输出
|
||
printf("Case %d: %lld\n", T++, res);
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
### 六、快速幂+$\_\_int128$
|
||
```cpp {.line-numbers}
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
#define int long long
|
||
#define endl "\n"
|
||
typedef unsigned __int128 INT128;
|
||
|
||
// 最大公约数
|
||
int gcd(int a, int b) {
|
||
if (b == 0) return a;
|
||
return b ? a : gcd(b, a % b);
|
||
}
|
||
|
||
// 快速幂+ INT128
|
||
int qmi(int a, int b, int mod) {
|
||
int res = 1;
|
||
while (b) {
|
||
if (b & 1) res = (INT128)res * a % mod;
|
||
a = (INT128)a * a % mod;
|
||
b >>= 1;
|
||
}
|
||
return res;
|
||
}
|
||
|
||
/**
|
||
* 功能：求单个数字的欧拉函数值
|
||
* @param x
|
||
* @return
|
||
*/
|
||
int phi(int x) {
|
||
int res = x;
|
||
for (int i = 2; i <= x / i; i++)
|
||
if (x % i == 0) {
|
||
res = res / i * (i - 1);
|
||
while (x % i == 0) x /= i;
|
||
}
|
||
if (x > 1) res = res / x * (x - 1);
|
||
return res;
|
||
}
|
||
|
||
signed main() {
|
||
int T = 1; // 准备输出Case i
|
||
int L;
|
||
while (cin >> L, L) {
|
||
int d = gcd(L, 8); // L和8的最大公约数 gcd(8,L)
|
||
int mod = 9 * L / d; // 公式推导得到的mod
|
||
int p = phi(mod); // 单个数字mod的欧拉函数值φ(mod)
|
||
int res = LONG_LONG_MAX; // 预求最小先设最大
|
||
|
||
if (gcd(mod, 10) > 1) // 判断p和10是否互质,不互质:方程无解，输出0
|
||
res = 0;
|
||
else {
|
||
for (int d = 1; d * d <= p; d++) // 枚举φ(p)的每个小约数,到sqrt(φ(p))
|
||
if (p % d == 0) { // 如果d是约数,那么其实我们一次发现了两个约数： d 和 phi/d
|
||
// 这里与原来的质因子分解有一点点不同，因为那个只要枚举小于sqrt(n)的，并且 n %d==0,
|
||
// 就一定是它的小质数因子，本题不是这个意思。
|
||
// 本题的目标是找出所有因子，注意，不是小因子。
|
||
// 因为，小因子不见得能是方程的解，大因子不见得不是方程的解！！
|
||
// 对于它们，都有机会成为答案，需要全部讨论到！然后PK最小值即可！
|
||
// 如果这个约数d，满足 10 ^ d ≡ 1 (mod p) ，那么它有机会成为答案
|
||
if (qmi(10, d, mod) == 1) res = min(res, d); // 小约数
|
||
// 如果这个约数phi/d，满足 10 ^ (phi/d) ≡ 1 (mod p) ，那么它有机会成为答案
|
||
if (qmi(10, p / d, mod) == 1) res = min(res, p / d); // 大约数
|
||
}
|
||
}
|
||
// 输出
|
||
printf("Case %d: %lld\n", T++, res);
|
||
}
|
||
}
|
||
``` |