ABC103 C - Modulo Summation

備忘録

問題

atcoder.jp

回答

import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def func(q, A):
    return sum(q % a for a in A)


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    q = 1
    for a in A:
        q *= a
    ret = func(q - 1, A)
    print(ret)


if __name__ == '__main__':
    main()

考え方

整数列Aの整数(a1, a2, a3 ..)に対して、最も大きな余りを得られる値は、
(a1 - 1) mod a1, (a2 - 1) mod a2, (a3 - 1) mod a3, ..である。
つまり、(a1 - 1) mod a1の(a1 - 1)はa1で割り切ることが出来る値から-1したものであり、
続くa2, a3...も同様である。
そのため、整数列Aの値をすべて乗算し、そこから-1した値が最も大きな余りを得られる値となる。
あとは求めた値で条件の計算を行うことで回答を得られる。