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

Пришлось тут на днях решать для студента (первого курса) задачку.

Дословно выглядит вот так:

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-го года :)

Конечно странно что такие вещи задают первокурснику, но...

В итоге для обкатки накидал такое решение на двух полусумматорах - банальная битовая арифметика:

#include "stdafx.h"

// хранилище для оооочень большого числа
unsigned char UInt128[16];

void printUInt128(){
 printf("result = 0x");
 for (int i = 15; i >= 0; i--)
  printf("%hhX", UInt128[i]);
 printf("\n");
}

// полный битовый сумматор реализующий таблицу истинности: http://ivatv.narod.ru/zifrovaja_texnika/1_04.htm
bool fullAdder(bool a, bool b, bool p0, bool *p){
 // первый полусумматор
 bool bRes = false;
 *p = false;
 if ((a && !b) || (b && !a))
  bRes = true;
 if (a && b)
  *p = true;
 if (!p0)
  return bRes;
 // второй полусумматор
 *p = true;
 bRes = !bRes;
 if (!a && !b)
  *p = false;
 return bRes;
}

// сумматор на битовых операциях
void add(long long x){
 bool pFlag = false;
 unsigned long long halfResult = 0; 
 unsigned long long bigValue;
 int i;
 bool aBit, bBit, sFlag;

 // получаем указатель на массив, содержащий большое число
 unsigned long long *p;
 p = (unsigned long long*)&UInt128[0];

 // берем младшие 8 байт
 bigValue = (unsigned long long)(*p);
 for (i = 0; i < 64; i++){
  // и побитно, посредством полного сумматора складываем два числа
  aBit = ((unsigned long long)1 << i & x) > 0;
  bBit = ((unsigned long long)1 << i & bigValue) > 0;
  sFlag = fullAdder(aBit, bBit, pFlag, &pFlag);
  if (sFlag)
   halfResult |= (unsigned long long)1 << i;
 };
 // результат помещаем обратно
 *p = halfResult;

 // если нет переноса бит от предыдущей операции, то можно выходить
 if (!pFlag)
  return;

 halfResult = 0;

 // сдвигаемся на 8 байт
 p++;

 // берем старшие 8 байт
 bigValue = (unsigned long long)(*p); 
 for (i = 0; i < 64; i++){
  // увеличиваем значение опираясь на бит переноса
  bBit = ((unsigned long long)1 << i & bigValue) > 0;
  sFlag = fullAdder(false, bBit, pFlag, &pFlag);
  if (sFlag)
   halfResult |= (unsigned long long)1 << i;
 };
 // результат помещаем обратно
 *p = halfResult;
}


int _tmain(int argc, _TCHAR* argv[])
{
 unsigned long long a, i;

 printf("enter value: ");
 scanf("%lld", &a);

 printf("calculating...\n");
 i = a;
 while(i > 0){
  add(a % i);
  i--;
 };
 printUInt128();

 getchar();
 getchar();

 return 0;
}

Либо, чтобы было проще понять, вариант на дельфи, но (увы) без коментариев:

program Project1;
 
{$APPTYPE CONSOLE}
 
{$R *.res}
 
uses
  Windows,
  SysUtils,
  Math;
 
type
  Int128 = array [0..15] of Byte;
 
var
  VeriBigInteger: Int128;
 
procedure PrintInt128;
var
  I: Integer;
begin
  Write('0x');
  for I := 15 downto 0 do
    Write(IntToHex(VeriBigInteger[I], 2));
  Writeln;
end;
 
function FullAdder(A, B, P0: Boolean; var P: Boolean): Boolean;
begin
  Result := False;
  P := False;
  if A and not B then
    Result := True;
  if B and not A then
    Result := True;
  if A and B then
    P := True;
  if not P0 then Exit;
  P := True;
  Result := not Result;
  if not A and not B then
    P := False;
end;
 
procedure Add(Value: Int64);
var
 I: Integer;
 ABit, BBit, SFlag, PFlag: Boolean;
 HalfResult, BigValue: Int64;
begin
 PFlag := False;
 HalfResult := 0;
 BigValue := PInt64(@VeriBigInteger[0])^;
 for I := 0 to 63 do
 begin
   ABit := (Int64(1) shl I and Value) > 0;
   BBit := (Int64(1) shl I and BigValue) > 0;
   SFlag := FullAdder(ABit, BBit, PFlag, PFlag);
   if SFlag then
      HalfResult := HalfResult or (Int64(1) shl I);
 end;
 PInt64(@VeriBigInteger[0])^ := HalfResult;
 
 HalfResult := 0;
 BigValue := PInt64(@VeriBigInteger[8])^;
 for I := 0 to 63 do
 begin
   BBit := (1 shl I and BigValue) > 0;
   SFlag := FullAdder(False, BBit, PFlag, PFlag);
   if SFlag then
      HalfResult := HalfResult or (Int64(1) shl I);
end;
 
 PInt64(@VeriBigInteger[8])^ := HalfResult;
end;
 
function TstNative(X: int64): int64;
var
  I: Int64;
begin
  I := X;
  Result := 0;
  while I > 0 do
  begin
    Result := Result + (X mod I);
    Dec(I);
  end;
end;
 
procedure TstOld(X: int64);
var
  I: Int64;
begin
  ZeroMemory(@VeriBigInteger[0], SizeOf(Int128));
  I := X;
  while I > 0 do
  begin
    Add(X mod I);
    Dec(I);
  end;
  PrintInt128;
end;
 
var
  N: int64;
begin
  try
  repeat
    Readln(N);
    Writeln('0x', IntToHex(TstNative(N), 32));
    TstOld(N);
  until N = 0;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
  readln;
end.

Сразу скажу - ЭТО работает, причем работает правильно (можно даже использовать для проверки), однако есть более грамотный и более быстрый вариант решения в 17 строчек кода, вместо процедур Add и FullAdder (на дельфи или на си - кому как удобнее) :)

Задача - попробовать найти данный вариант решения или предложить еще более оптимальный вариант :)

С наступающим :)

UPD: дам подсказку, график прохода по модулю выглядит вот так:

Определение верхнего лимита прогрессии:

X := Limit div (Z + 1) - (Z - (Limit mod (Z + 1)));
Где:
X - предел положительной вершины
Limit - значение числа N из оригинальной задачи
Z - текущее прирастание прогрессии (т.е. при Z = 1, прогрессия 0, 1, 2... при Z = 5, прогрессия 0, 5, 10... )

т.е. грубо идем от 0 до 1000 - пики выглядят:

499, 332, 247, 196, 165 и т.д....