четверг, 25 декабря 2014 г.

Предновогодняя задачка для разминки мозга

Пришлось тут на днях решать для студента (первого курса) задачку.
Дословно выглядит вот так:
2014 ACM-ICPC China Hunan Invitational Programming Contest
There is a simple problem. Given a number N.
You are going to calculate N%1+ N%2+ N%3+...+ N%N.
Input: The length N(1<=N<=10^12).
Output: Answer.
Sample input 5
Sample output 4
Вроде ничего сложного, однако-ж результат суммирования по модулю явно не уложится ни в один из поддерживаемых типов (int64 максимум 8 байт).

Сразу уточню: задачка олимпиадная, причем свежего 14-го года :)