CADDi 2018 C - Product and GCD
備忘録
問題
回答
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 prime_fact(N): n = 2 prime = [] while n * n <= N: i = 0 while N % n == 0: N //= n i += 1 if i > 0: prime.append((n, i)) n += 1 if N != 1: prime.append((N, 1)) return prime def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N, P = il() # 素因数分解 prime = prime_fact(P) # 各素因数(q)をN個の要素(a1, a2, ... , an)に振り分ける ret = 1 for p, k in prime: q = p ** (k//N) if q == 0: continue else: ret *= q print(ret) if __name__ == '__main__': main()
考え方
素因数分解を用いて回答を求める問題です。
- 回答概要
P
の素因数分解を行う- 各素因数を
N
個の整数(a1, a2, ... , an
)に振り分ける
N
個の整数(a1, a2, ... , an
)から求める最大公約数について考えます。
P
はN
個の整数によって求めることが出来ます。
N
個の整数から最大公約数(g
)を求めるため、P
は求める最大公約数(g
)の倍数です。
P = a1 * a2 * ... * an = g ** k
最大公約数を出来る限り大きくするためには、P
を各a
にできる限り均等に振り分ける必要があります。
P
を均等に振り分けるために、P
の素因数分解を行います。
P
を素因数分解することによって、P
を構成する素因数と素因数の数を求めることが出来ます。
P = p1 ** k1 + p2 ** k2 + ... + pn ** kn
この各素因数p
をN
個に均等に振り分けることによって、最大公約数を求めることが出来ます。