AtCoder Regular Contest 149 - A - Repdigit Number
Time Limit: 2 sec / Memory Limit: 1024 MB
Score :
Problem Statement
You are given positive integers
is a positive integer less than , and all digits in the decimal representation of are the same. is a multiple of .
If no positive integer -1
.
Constraints
Input
The input is given from Standard Input in the following format:
Output
Print the maximum positive integer -1
if no such positive integer
Sample Input 1
7 12
Sample Output 1
888888
Four positive integers
Sample Input 2
9 12
Sample Output 2
888888888
Six positive integers
Sample Input 3
1 3
Sample Output 3
9
Three positive integers
Sample Input 4
1000 25
Sample Output 4
-1
No positive integers
Sample Input 5
30 1
Sample Output 5
999999999999999999999999999999
题目大意
给你两个正整数11111...1
的数,其中这个数不大于
解题思路
首先想想怎么暴力。暴力的话,Python自带大整数,而C++则需要手写高精度。
以数字1为例,那么暴力无非就是:
- 从
1
开始尝试,接着尝试11
、111
、...
、1111...1
,看看哪个数能整除 。如果能整除 ,就更新答案的最大值。
但是这样肯定超时,因为1111...1
(100000个1)。
构造出这个有100000个1的数字,再让它除以
从
那么,有没有一种办法,能够优化一个维度呢?有没有办法不适用大整数,而是直接使用64位整数(如C语言的long long)存下整个运算过程的结果呢?
这让我们想到了取模。
取模有以下两种性质:
说人话就是:加法和乘法运算不改变取模结果。
取模好啊,取模后,就能用64位整数存下了。
在计算过111的基础上,有没有办法,在
同时,
所以,问题解决啦!
先考虑1
、11
、...
、11...1
, 从1
开始,然后在1
的结果上计算11
,再在11
的基础上计算111
,直到计算到1
为止。
1 |
|
如果中间过程中,取模结果为0,那么就更新答案的最大值(记录下来是多少个几)
之后考虑222...2
、333..3
、...
、999..9
最后输出
总时间复杂度
AC代码
1 |
|
同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/127149808