시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 566 138 91 22.141%

문제

오늘 사탕 M개를 가득 담은 박스가 택배로 택희네 집에 도착했다. 택희는 이 사탕을 N명의 친구들에게 나누어 주려고 한다.

택희의 친구들은 문자로 사탕을 몇 개 받고 싶은지 보냈다. 만약 받고 싶은 개수만큼 사탕을 받지 못한다면, 그 친구는 분노하게 되고, 못 받는 개수가 많아질 수록 더욱 분노하게 된다.

놀랍게도 택희는 친구들의 분노를 수치화 할 수 있는데, 이것은 못 받는 사탕 개수의 제곱이다.

예를 들어, 택희의 친구 백준이가 받고 싶은 사탕의 개수가 32개였을 때, 사탕을 29개 받아 3개를 받지 못한다면, 그의 분노는 3의 제곱 9가 된다.

택희가 받은 사탕의 개수와 친구의 수, 그리고 그 친구들이 받고 싶어하는 사탕의 개수가 주어졌을 때, 사탕을 적절히 나누어 주어 친구들의 분노의 합을 최소화해 그 값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 M(1 ≤ M ≤ 2×109)와 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 친구들이 받고 싶어하는 사탕의 개수가 주어진다. 이 개수는 2×109보다 작으며, 친구들이 받고 싶어하는 사탕의 개수의 합은 항상 M을 넘는다.

출력

첫째 줄에 택희 친구들의 분노의 합의 최소값을 264로 나눈 나머지를 출력한다.

예제 입력 1

5 3
1
3
2

예제 출력 1

1
W3sicHJvYmxlbV9pZCI6IjI4NzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlOTRcdWI1MTRcdWNlOTRcdWI1MTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzYyNFx1YjI5OCBcdWMwYWNcdWQwZDUgTVx1YWMxY1x1Yjk3YyBcdWFjMDBcdWI0ZGQgXHViMmY0XHVjNzQwIFx1YmMxNVx1YzJhNFx1YWMwMCBcdWQwZGRcdWJjMzBcdWI4NWMgXHVkMGRkXHVkNzZjXHViMTI0IFx1YzlkMVx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1ODhcdWIyZTQuIFx1ZDBkZFx1ZDc2Y1x1YjI5NCBcdWM3NzQgXHVjMGFjXHVkMGQ1XHVjNzQ0IE5cdWJhODVcdWM3NTggXHVjZTVjXHVhZDZjXHViNGU0XHVjNWQwXHVhYzhjIFx1YjA5OFx1YjIwNFx1YzViNCBcdWM4ZmNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQwZGRcdWQ3NmNcdWM3NTggXHVjZTVjXHVhZDZjXHViNGU0XHVjNzQwIFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWMwYWNcdWQwZDVcdWM3NDQgXHViYTg3IFx1YWMxYyBcdWJjMWJcdWFjZTAgXHVjMmY2XHVjNzQwXHVjOWMwIFx1YmNmNFx1YjBjOFx1YjJlNC4gXHViOWNjXHVjNTdkIFx1YmMxYlx1YWNlMCBcdWMyZjZcdWM3NDAgXHVhYzFjXHVjMjE4XHViOWNjXHVkMDdjIFx1YzBhY1x1ZDBkNVx1Yzc0NCBcdWJjMWJcdWM5YzAgXHViYWJiXHVkNTVjXHViMmU0XHViYTc0LCBcdWFkZjggXHVjZTVjXHVhZDZjXHViMjk0IFx1YmQ4NFx1YjE3OFx1ZDU1OFx1YWM4YyBcdWI0MThcdWFjZTAsIFx1YmFiYiBcdWJjMWJcdWIyOTQgXHVhYzFjXHVjMjE4XHVhYzAwIFx1YjljZVx1YzU0NFx1YzljOCBcdWMyMThcdWI4NWQgXHViMzU0XHVjNmIxIFx1YmQ4NFx1YjE3OFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjE4MFx1Yjc4ZFx1YWM4Y1x1YjNjNCBcdWQwZGRcdWQ3NmNcdWIyOTQgXHVjZTVjXHVhZDZjXHViNGU0XHVjNzU4IFx1YmQ4NFx1YjE3OFx1Yjk3YyBcdWMyMThcdWNlNThcdWQ2NTQgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1Yzc3NFx1YWM4M1x1Yzc0MCBcdWJhYmIgXHViYzFiXHViMjk0IFx1YzBhY1x1ZDBkNSBcdWFjMWNcdWMyMThcdWM3NTggXHVjODFjXHVhY2YxXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWQwZGRcdWQ3NmNcdWM3NTggXHVjZTVjXHVhZDZjIFx1YmMzMVx1YzkwMFx1Yzc3NFx1YWMwMCBcdWJjMWJcdWFjZTAgXHVjMmY2XHVjNzQwIFx1YzBhY1x1ZDBkNVx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgMzJcdWFjMWNcdWM2MDBcdWM3NDQgXHViNTRjLCBcdWMwYWNcdWQwZDVcdWM3NDQgMjlcdWFjMWMgXHViYzFiXHVjNTQ0IDNcdWFjMWNcdWI5N2MgXHViYzFiXHVjOWMwIFx1YmFiYlx1ZDU1Y1x1YjJlNFx1YmE3NCwgXHVhZGY4XHVjNzU4IFx1YmQ4NFx1YjE3OFx1YjI5NCAzXHVjNzU4IFx1YzgxY1x1YWNmMSA5XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMGRkXHVkNzZjXHVhYzAwIFx1YmMxYlx1Yzc0MCBcdWMwYWNcdWQwZDVcdWM3NTggXHVhYzFjXHVjMjE4XHVjNjQwIFx1Y2U1Y1x1YWQ2Y1x1Yzc1OCBcdWMyMTgsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFkZjggXHVjZTVjXHVhZDZjXHViNGU0XHVjNzc0IFx1YmMxYlx1YWNlMCBcdWMyZjZcdWM1YjRcdWQ1NThcdWIyOTQgXHVjMGFjXHVkMGQ1XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMwYWNcdWQwZDVcdWM3NDQgXHVjODAxXHVjODA4XHVkNzg4IFx1YjA5OFx1YjIwNFx1YzViNCBcdWM4ZmNcdWM1YjQgXHVjZTVjXHVhZDZjXHViNGU0XHVjNzU4IFx1YmQ4NFx1YjE3OFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjZDVjXHVjMThjXHVkNjU0XHVkNTc0IFx1YWRmOCBcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE0oMSAmbGU7Jm5ic3A7TSAmbGU7IDImdGltZXM7MTA8c3VwPjk8XC9zdXA+KVx1YzY0MCBOKDEgJmxlOyBOICZsZTsgMTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NzQgXHViYzFiXHVhY2UwIFx1YzJmNlx1YzViNFx1ZDU1OFx1YjI5NCBcdWMwYWNcdWQwZDVcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YWMxY1x1YzIxOFx1YjI5NCAyJnRpbWVzOzEwPHN1cD45PFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3M2NcdWJhNzAsIFx1Y2U1Y1x1YWQ2Y1x1YjRlNFx1Yzc3NCBcdWJjMWJcdWFjZTAgXHVjMmY2XHVjNWI0XHVkNTU4XHViMjk0IFx1YzBhY1x1ZDBkNVx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NTggXHVkNTY5XHVjNzQwIFx1ZDU2ZFx1YzBjMSBNXHVjNzQ0IFx1YjExOFx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDBkZFx1ZDc2YyBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NTggXHViZDg0XHViMTc4XHVjNzU4IFx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgMjxzdXA+NjQ8XC9zdXA+XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4NzgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMSlVUTkpBIiwiZGVzY3JpcHRpb24iOiI8cD5DaGlsZHJlbiBpbiBhIGtpbmRlcmdhcnRlbiBoYXZlIHJlY2VpdmVkIGEgbGFyZ2Ugc2FjayBjb250YWluaW5nIE0gY2FuZGllcy4gSXQgaGFzIGJlZW4gZGVjaWRlZCB0aGF0IHRoZSBjYW5kaWVzIGFyZSB0byBiZSBkaXN0cmlidXRlZCBhbW9uZyBOIGNoaWxkcmVuLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIGNoaWxkIGhhcyBzdGF0ZWQgdGhlIG51bWJlciBvZiBjYW5kaWVzIHRoYXQgaXQgd2FudHMuIElmIGEgY2hpbGQgaXNuJnJzcXVvO3QgZ2l2ZW4gdGhlIGFtb3VudCBvZiBjYW5keSBpdCB3YW50cywgaXQgd2lsbCBnZXQgYW5ncnkuIEluIGZhY3QgaXQmcnNxdW87bGwgZ2V0IGFuZ3JpZXIgZm9yIGVhY2ggY2FuZHkgaXQgaXMgZGVwcml2ZWQgb2YuIFNvbWUgc3BlY3VsYXRlIHRoYXQgaXQmcnNxdW87cyBhbmdlciB3aWxsIGJlIGVxdWFsIHRvIHRoZSBzcXVhcmUgb2YgdGhlIG51bWJlciBvZiBjYW5keSBpdCBpcyBkZXByaXZlZCBvZi4gRm9yIGluc3RhbmNlLCBpZiBNaXJrbyBzdGF0ZXMgdGhhdCBoZSB3YW50cyAzMiBjYW5kaWVzIGJ1dCByZWNlaXZlcyBvbmx5IDI5LCBoZSB3b3VsZCBiZSBtaXNzaW5nIDMgY2FuZGllcywgc28gaGlzIGFuZ2VyIHdvdWxkIGJlIGVxdWFsIHRvIDkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlVuZm9ydHVuYXRlbHksIHRoZXJlIGlzIGFuIGluc3VmZmljaWVudCBhbW91bnQgb2YgY2FuZHkgdG8gc2F0aXNmeSBhbGwgY2hpbGRyZW4uIFRoZXJlZm9yZSwgdGhlIGNhbmRpZXMgc2hvdWxkIGJlIGRpc3RyaWJ1dGVkIGluIHN1Y2ggYSB3YXkgdGhhdCB0aGUgc3VtIG9mIHRoZSBjaGlsZHJlbiZyc3F1bztzIGFuZ2VyIGlzIG1pbmltYWwuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMsIE0gKDEgJmxlOyBNICZsZTsgMiZtaWRkb3Q7MTA8c3VwPjk8XC9zdXA+KSBhbmQgTiAoMSAmbGU7IE4gJmxlOyAxMDAgMDAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW4gaW50ZWdlcnMgKG9uZSBwZXIgbGluZSkgd2hpY2ggcmVwcmVzZW50IHRoZSB3aXNoZXMgb2YgdGhlIGNoaWxkcmVuLiBUaG9zZSBudW1iZXJzIGFyZSBhbGwgc3RyaWN0bHkgbGVzcyB0aGFuIDImbWlkZG90OzEwPHN1cD45PFwvc3VwPiwgYW5kIHRoZWlyIHN1bSBhbHdheXMgZXhjZWVkcyBNLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #1 4번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: choiking10
  • 잘못된 조건을 찾은 사람: jh05013