DE
RU
EN
ES
ZH
FR
PT
AR
HI
Berechnung des maximalen Produkts einer Teilfolge mit Zerlegung in Primfaktoren
TypeScript
Hard
math
Aufgabe «Berechnung des maximalen Produkts einer Teilfolge mit Zerlegung in Primfaktoren»
Gegeben ist eine Folge ganzer Zahlen a1, a2, ..., an. Es soll das maximale Produkt einer Teilfolge (nicht notwendigerweise zusammenhängend) der Länge k gefunden werden, wobei k vorgegeben ist. Dabei ist es erlaubt, Elemente in ihre Primfaktoren zu zerlegen, jedoch höchstens einmal pro Element. Das bedeutet, für jedes Element kann man es entweder vollständig nehmen oder durch einen seiner Primfaktoren ersetzen (falls es keine Primzahl ist), und erst dann im Produkt verwenden. Falls ein Element eine Primzahl ist, kann man es nur vollständig nehmen oder weglassen. Gesucht ist das größtmögliche Produkt modulo 10^9+7.
Eingabeformat
Die erste Zeile enthält zwei ganze Zahlen n und k (1 ≤ k ≤ n ≤ 1000). Die zweite Zeile enthält n ganze Zahlen a_i (2 ≤ a_i ≤ 10^9).
Ausgabeformat
Geben Sie eine ganze Zahl aus — das maximale Produkt modulo 10^9+7.
main.ts