Problemas
크리스마스를 맞이하여 산타 할아버지는 전 세계의 착한 어린이 K명에게 인형을 사주려고 한다.
산타 할아버지는 인형을 구입하기 위해 인형가게에 들어왔다.
가게에는 N개의 인형 상자가 한 줄로 진열되어 있고, 각 인형 상자에는 한 개 이상의 인형이 들어 있다.
그리고 인형가게에서는 주문의 편의성을 위해 각 상자에 번호를 붙여 놓았고,
주문은 "H번 상자부터 T번 상자까지 다 주세요."라고만 할 수 있다. (H≤T)
산타 할아버지는 한 번 주문할 때마다, 주문한 상자에 있는 인형들을 모두 꺼내서
각각을 K명에게 정확히 같은 수만큼 나누어 주고, 남는 인형이 없도록 한다.
1. 한 번 주문할 수 있다면, 가능한 주문 방법은 몇 가지인가? 2. 여러 번 주문할 수 있다면, 주문이 겹치지 않게 최대 몇 번 주문할 수 있는가? (주문이 겹친다는 것은 어떤 두 주문에 같은 번호의 인형 상자가 포함되는 것을 말한다.)
Entrada
입력의 첫 번째 줄에는 인형 상자의 개수 N과 어린이의 수 K가 주어진다.(1≤N, K≤100,000)
입력의 두 번째 줄에는 1번 인형 상자부터 N번 인형 상자까지 각 인형 상자에 들어 있는 인형의 개수 Di가 주어진다.
( 1≤i≤N, 1≤Di≤100,000 )
Salida
1번에 대한 답과 2번에 대한 답을 한 줄에 하나의 빈칸으로 나누어 출력한다.
1번 답은 매우 클 수 있으므로 20,091,101로 나눈 나머지를 출력한다.
Ejemplo #1
6 4
1 2 3 4 5 6
3 1
Ejemplo #2
9 3
1 2 3 4 5 6 7 8 9
24 6
Fuente
AOJ
Debes iniciar sesión para escribir código.