程序必须接受一个整数N作为输入。程序必须打印出N中由一系列连续出现的数字(按相同顺序)组成的所有Proonic整数作为输出。
这个整数可以表示为n *(n +1)。
- 注意:必须按出现的顺序打印Proonic整数。**
- 边界条件:**
- 1〈= N〈= 10^20**
最大执行时间:4000毫秒
- 1〈= N〈= 10^20**
- 输入格式:**第一行包含N。*输出格式:第一行包含由空格分隔的Proonic整数。示例输入/输出1: * 输入:
93042861
- 输出:**
九三○三十○四十二二十六
- 说明:**
30 * 31 = 930人
5 * 6 = 30
0 * 1 = 0
6 * 7 = 42
1 * 2 = 2
2 * 3 = 6
- 示例输入/输出2:**
- 输入:**
247025123524
- 输出:**
二702 0 2 12
- 说明:**
1 * 2 = 2
二十六 * 二十七=七百零二
0 * 1 = 0
1 * 2 = 2
3 * 4 = 12
1 * 2 = 2
四十八 * 四十九=二千三百五十二
1 * 2 = 2
def ispro(n):
for i in range(n+1):
if i*(i+1)==n: return 1
return 0
def pro(a):
n=len(a)
for i in range(n):
for j in range(n):
if(a[i:j]!=""):
if(a[i:j]==str(int(a[i:j]))):
if(ispro(int(a[i:j]))):
print(a[i:j],end=" ")
a=input().strip()
pro(a)
- 在此代码中,字符串长度大于10时超过时间限制。**
您可以编辑此代码或创建自己的代码来解决此问题。
- 在此代码中,字符串长度大于10时超过时间限制。**
1条答案
按热度按时间bxjv4tth1#
N = 10^20意味着有20个可能的数字。这意味着我们必须检查20 *(19)/ 2 --〉190个可能的数字来检查它们是否是前凸的。让我们把这20个可能的数字中的一个表示为PRN。
PRN的最大位数是20 --显然我们不能对每个可能的数字都进行暴力破解(这需要10^20次迭代),而是可以在N上进行二分搜索,其中N *(N+1)= PRN。
如果你还不知道二分查找,你可以搜索二分查找来了解更多。本质上,如果我们的猜测(N)太大,我们就把N变小,否则我们就把N变大。我们一直这样做,直到N *(N+1)= PRN(意味着PRN是Proonic),或者没有可能的解--所以我们继续。
这种二分查找将花费log(n)时间。因此,对于最多20位数字,需要67次迭代。对于超过190个可能的数字,这将是12730次检查-这将很容易适应时间限制。可能有更多数学上漂亮的解决方案,但这将是做。