题解 P2841 【A*B Problem】

· · 题解

看上去没有人暴力...

一道bfs居然被我做成了暴力！

主要思想：二进制枚举

\text{因为都是01串，和二进制一样，所以我们可以枚举二进制数}

语言：Py3

\text{高精嘛。。。而且Py有bin函数，可以转二进制}

注意：

bin$函数转化的形式是“0b...”，所以我们可以使用$Py$的字符串切片，即：$s \left[x:y:z\right]$，得到的字符串是在下标$\left[x,y\right)$ 中，每$z$个步长取一个字符组成的字符串，而如果有的项不填，会设为默认值，默认值为：$x=0,y=len(s),z=1$。那么同理，切片$bin$转化后的字符串为$s\left[2:\right]

于是你就会交这个代码： 

n=int(input())
p=1
s='1'
while int(s)%n!=0: #枚举
    s=bin(p)
    s=s[2:]
    p+=1
print(str(int(s)//n),s)

80Pts?!T了两个点？？？

一点优化：

我们注意到，如果n为偶数时，它的倍数只能是偶数，也就是二进制以0结尾，那么我们只枚举偶数p。
其次，5的倍数如此，n为5的倍数也可以带进去
然后你交了这个代码：

n = int(input())
if n % 2 == 0 or n % 5 == 0: #2或5倍数
    p = 2
    s = '10'
    while int(s) % n != 0:
        s = bin(p)
        s = s[2:]
        p += 2
    print(int(s) // n, s)
else:
    p = 1
    s = '1'
    while int(s) % n != 0:
        s = bin(p)
        s = s[2:]
        p += 1
    print(int(s) // n, s)

还是80Pts?!

又一点优化：

我耐心地把很多数带进程序，发现n全是9时跑得最慢，连99都比9998慢，那么全是9的又有什么性质呢？
可以发现，全是9时时它的答案全是1！
证明：略（逃
利用这个性质，基本上就可以A掉本题了，我不知道再大一点有没有这个性质（逃，那么根据99...99的倍数性质，可以直接得出答案：

ans=\begin{matrix}\underbrace{11 \cdots 11}\\len(str(n))\times 9\text{个1}\end{matrix}

100Pts代码：

n = int(input())
a = str(n).count('9')
if a == len(str(n)):
    s=''
    for i in range(a * 9):
        s+='1'
    print(int(s)//n,s)
elif n % 2 == 0 or n % 5 == 0:
    p = 2
    s = '10'
    while int(s) % n != 0:
        p += 2
        s = bin(p)
        s = s[2:]
    print(int(s) // n, s)
else:
    p = 1
    s = '1'
    while int(s) % n != 0:
        p += 1
        s = bin(p)
        s = s[2:]
    print(int(s) // n, s)

这是（暂时）Py3的最优解哦