7-38 數(shù)列求和-加強(qiáng)版 (20 分)

給定某數(shù)字A（1≤A≤9）以及非負(fù)整數(shù)N（0≤N≤100000），求數(shù)列之和S=A+AA+AAA+?+AA?A（N個(gè)A）。例如A=1, N=3時(shí)，S=1+11+111=123。

輸入格式：

輸入數(shù)字A與非負(fù)整數(shù)N。

輸出格式：

輸出其N項(xiàng)數(shù)列之和S的值。

輸入樣例：

1 3

輸出樣例：

123

一開始的解題思路：

一開始想得很簡單，直接用加法。
python 不用考慮數(shù)字會(huì)溢出，所以直接加非常方便。
但是最大示例有100000個(gè)，最后的最大數(shù)字用例測試會(huì)超時(shí)。

代碼參考：

a,n = map(int,input().split())
num = 0
sum = 0
for i in range(n):
    num += a * (10**i)
    sum += num
print(sum)

經(jīng)過參考其他人的代碼后，修改為如下解法，用數(shù)組存儲(chǔ)，節(jié)省時(shí)間。

最終優(yōu)化結(jié)果：

思路是建一個(gè)比 n+1 位的數(shù)組（因?yàn)椴还躠和n是多少，最終一定會(huì)有n位數(shù)，還有可能會(huì)比n位數(shù)更多，所以n位用來存放單個(gè)的數(shù)字，表示該位的值，多出來的那一位數(shù)就用來存儲(chǔ)進(jìn)位的數(shù)（這時(shí)不管是進(jìn)位一位數(shù)還是兩位數(shù)都無所謂了）。
提交時(shí)偶爾會(huì)超時(shí)，但是有時(shí)也能過。還有進(jìn)一步優(yōu)化效率的空間。

a,n = map(int,input().split())
#這時(shí)候要考慮n==0的情況
if n == 0:
    print(0)
else:
    lt = ['']*(n+1)
    temp = 0
    remain = 0

    for i in range(n):
        temp = a * (n-i) + remain       #從個(gè)位開始算，相應(yīng)的位和為a*(n-i)，再加上一位的進(jìn)位數(shù)remain
        lt[ -i - 1] = str(temp % 10)    #取個(gè)位放在從后往前數(shù)的第 i+1 位，即 -i-1，str()轉(zhuǎn)字符方便輸出
        remain = temp // 10             #去掉個(gè)位就是進(jìn)位
        if remain and i == n-1:         #這個(gè)是最后一位了，不用加了，如果不是0就直接存儲(chǔ)到數(shù)組第一位
            lt[ -n - 1] = str(remain)   #str()轉(zhuǎn)字符方便輸出
    print(''.join(lt))                  #用''拼接，必須要str才能操作，所以前面加了str()

其他人參考資料：

PTA 7-38 數(shù)列求和-加強(qiáng)版 (20 分) python版
這個(gè)數(shù)組里存儲(chǔ)的不是直接結(jié)果，讓我感覺不是很爽，不過效率貌似比我的要高一些。

a,n=map(int,input().split())
add=0
l=[0]*100000
if n==0:
    print("0")
for i in range(n,0,-1):
    add=(i*a+add)//10
    l[i-1]=add
if add!=0:
    print(add,end='')
for i in range(1,n+1):
    if n==i:
        print((i*a)%10,end='')
    else:
        print((i*a+l[i])%10,end='')

數(shù)列求和——加強(qiáng)版 Python
這個(gè)我提交時(shí)還是會(huì)超時(shí)，不過從他這學(xué)了 ''.join 的拼接語法

a,b=map(int,input().split())
if b==0:
    print(0)
else:
    lt=[];c=0;w=1
    for i in range(b):
         lt.append((a*(b-i)+c)%10)
         c=(a*(b-i)+c)//10
         w+=1
         if c and i==b-1:
             lt.append(c)
    print(''.join(list(map(str,lt[::-1]))))