ABC103 C - Modulo Summation
備忘録
問題
回答
import sys import os import math import bisect import collections import itertools import heapq 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)] lcm = lambda x, y: x * y / math.gcd(x, y) MOD = 10 ** 9 + 7 MAX = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N = ii() A = il() q = 1 for a in A: q *= a print(sum((q-1) % a for a in A)) if __name__ == '__main__': main()
考え方
全ての整数を乗算した値は、N
個全ての整数で割り切ることができる。
そのため、整数を乗算した値から1
を引くことで、
割り切ることが出来ない、最も大きな値になる。
あとはその値を全て足すことが回答となる。
上記のコードではO(N*2)
の計算量となっているが、
単純に各整数から1
を引いた値を全て足すことでO(N)
で回答することができる。
(各整数a
から1
を引いた値が割り切れず最も大きな余りの値となるため)
O(N)
回答例:
Submission #12896519 - AtCoder Beginner Contest 103