備忘録
問題
回答
import sys import os import math import bisect import itertools import collections import heapq import queue import array import time # 時々使う # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall # from decimal import Decimal # from collections import defaultdict, deque # 再帰の制限設定 sys.setrecursionlimit(10000000) def ii(): return int(sys.stdin.buffer.readline().rstrip()) def il(): return list(map(int, sys.stdin.buffer.readline().split())) def fl(): return list(map(float, sys.stdin.buffer.readline().split())) def iln(n): return [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] def iss(): return sys.stdin.buffer.readline().decode().rstrip() def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split())) def isn(n): return [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] def lcm(x, y): return (x * y) // math.gcd(x, y) MOD = 10 ** 9 + 7 INF = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N = ii() N -= 1 print(((N + 1) * N) // 2) if __name__ == '__main__': main()
考え方
数列の法則について考察する問題です。
余りM
を最大限大きくするための数列P
について考えます。
- 回答概要
- 各
i
はi+1
となるP
で余りの最大値を得ることが出来る N
以外の1, 2, ... , N-1
は余りの最大値を得ることがで出来る
- 各
まず各i
の余りを最大にするP
について考えます。
i = 1
のとき、P >= 2
であれば、M = 1
となりこれ以上のM
を得ることはできません。i = 2
のとき、P >= 3
であれば、M = 2
となりこれ以上のM
を得ることはできません。
以上のように、i
の余りを最大にするためには、P <= i + 1
である必要があります。
また、i + 1
以上大きい値でも余りM
の値は変化しないため、
P
はi + 1
が最適であることがわかります。
このことから、i = {1, 2, 3, ... , N}
に対して
最適なP
は{2, 3, 4, ... , N-1, 1}
となります。
この時のM
は{1, 2, 3, ... , N - 1}
となるため、
合計値は1
からN-1
までの和をO(1)
で求めることが出来ます。