AtCoder Regular Contest 149 - A - Repdigit Number

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $300$ points

Problem Statement

You are given positive integers $N$ and $M$. Find the maximum positive integer $X$ that satisfies all of the following conditions.

• $X$ is a positive integer less than $10^N$, and all digits in the decimal representation of $X$ are the same.
• $X$ is a multiple of $M$.

If no positive integer $X$ satisfies the conditions, print -1.

Constraints

• $1\leq N\leq 10^5$
• $1\leq M\leq 10^9$

---

Input

The input is given from Standard Input in the following format:

$N$ $M$

Output

Print the maximum positive integer $X$ that satisfies all of the conditions, or -1 if no such positive integer $X$ exists.

---

Sample Input 1

7 12

Sample Output 1

888888

Four positive integers $X$ satisfy the conditions: $444, 888, 444444, 888888$. The answer is the maximum of them, which is $888888$.

---

Sample Input 2

9 12

Sample Output 2

888888888

Six positive integers $X$ satisfy the conditions: $444, 888, 444444, 888888, 444444444, 888888888$.

---

Sample Input 3

1 3

Sample Output 3

9

Three positive integers $X$ satisfy the conditions: $3, 6, 9$.

---

Sample Input 4

1000 25

Sample Output 4

-1

No positive integers $X$ satisfy the conditions.

---

Sample Input 5

30 1

Sample Output 5

999999999999999999999999999999

题目大意

给你两个正整数$N$和$M$，让你找到最大的 形如11111...1的数，其中这个数不大于$N$，并且这个数能被$M$整除

解题思路

首先想想怎么暴力。暴力的话，Python自带大整数，而C++则需要手写高精度。

以数字1为例，那么暴力无非就是：

• 从1开始尝试，接着尝试11、111、...、1111...1，看看哪个数能整除$M$。如果能整除$M$，就更新答案的最大值。

但是这样肯定超时，因为$N$的最大值是$10^5$，也就是说最多尝试到1111...1(100000个1)。

构造出这个有100000个1的数字，再让它除以$M$，光是这一步的时间复杂度就是$O(N)$了

从$1$个1到$N$个1,时间复杂度同样是$O(N)$，因此，总时间复杂度为$O(N^2)$。

那么，有没有一种办法，能够优化一个维度呢？有没有办法不适用大整数，而是直接使用64位整数（如C语言的long long）存下整个运算过程的结果呢？

这让我们想到了取模。

取模有以下两种性质：

1. $(x+y)% MOD = ((x % MOD) +(y% MOD))%MOD$
2. $(x\times y)% MOD = ((x % MOD) \times (y% MOD))%MOD$

说人话就是：加法和乘法运算不改变取模结果。

取模好啊，取模后，就能用64位整数存下了。

在计算过111的基础上，有没有办法，在$O(1)$的时间复杂度内，计算出1111的结果呢？

$1111 = 111 * 10 + 1$，$1111 % M = ((111 % M) * 10 + 1) % M$

同时，$111…1$能整除$M$，等价于$111…1 % M = 0$

所以，问题解决啦！

先考虑1、11、...、11...1， 从1开始，然后在1的结果上计算11，再在11的基础上计算111，直到计算到$N$个1为止。

for (int j = 0; j < n; j++) {
    num = num * 10 + i;
    num %= MOD;
    if (num == 0) {
        更新答案最大值，记录下来是j个i
    }
}

如果中间过程中，取模结果为0，那么就更新答案的最大值（记录下来是多少个几）

之后考虑222...2、333..3、...、999..9

最后输出$j$个$i$即可

总时间复杂度$O(N)$，空间复杂度$O(1)$

---

AC代码

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
int main() {
    int n, m;
    cin >> n >> m;
    int maxI = -1, maxJ = -1;
    for (int i = 1; i < 10; i++) {
        ll num = i;
        for (int j = 0; j < n; j++) {
            num %= m;
            if (num == 0) {
                if (j + 1 >= maxJ) {
                    maxI = i, maxJ = j + 1;
                }
            }
            num = num * 10 + i;
        }
    }
    if (maxI == -1) {
        puts("-1");
        return 0;
    }
    for (int i = 0; i < maxJ; i++) {
        putchar('0' + maxI);
    }
    return 0;
}

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/127149808