题解：UVA10523 Very Easy !!!

· · 题解

非常简单的题目，直接模拟就可以了。

考虑小优化之后，抛开高精度之后复杂度是 O(n) 的，完全没有问题。

高精度并不是什么很有技术的事情，所以直接给出 Python 代码，也更加方便理解。

import sys
seq=sys.stdin.readlines()
for _ in seq:
    n,a=map(int,_.split(' '))
    ans=0
    k=1
    for __ in range(n):
        k*=a
        ans+=(__+1)*k
    print(ans)

但是实际上这里可以直接使用公式。

我们记要求的和式 \displaystyle\sum_{i=1}^ni\cdot a^i=S。 则

aS=\sum_{i=1}^ni\cdot a^{i+1} \newline S-aS=\left(\sum_{i=1}^{n}a_i\right)-na^{n+1} \newline S=\displaystyle\frac{\displaystyle\left(\sum_{i=1}^{n}a_i\right)-na^{n+1}}{1-a}

而且这里是没有任何取模运算的，所以可以直接用等比数列的求和公式算，就像这样：

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return

    idx = 0
    results = []
    while idx < len(data):
        n = int(data[idx])
        a = int(data[idx+1])
        idx += 2
        if a == 1:
            ans = n * (n + 1) // 2
        else:
            an = pow(a, n)
            an1 = an * a a^{n+1}
            numerator = a * (1 - (n + 1) * an + n * an1)
            denominator = (1 - a) * (1 - a)
            ans = numerator // denominator
        results.append(str(ans))

    print("\n".join(results))

if __name__ == "__main__":
    main()

这个就跑的飞快了，比常规的 C++ 高精度版本还快的多。

如果还要更快，就只能祭出我 C++ 了。

C++ 代码。