95 lines
1.9 KiB
ObjectPascal
95 lines
1.9 KiB
ObjectPascal
program gapful;
|
|
{$IFDEF FPC}
|
|
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
|
|
{$ELSE}
|
|
{$APPTYPE CONSOLE}
|
|
{$ENDIF}
|
|
uses
|
|
sysutils,// IntToStr
|
|
strUtils;// Numb2USA aka commatize
|
|
|
|
var
|
|
LCMsHL : array of NativeInt;
|
|
|
|
function GCD(a, b: Int64): Int64;
|
|
var
|
|
temp: Int64;
|
|
begin
|
|
while b <> 0 do
|
|
begin
|
|
temp := b;
|
|
b := a mod b;
|
|
a := temp
|
|
end;
|
|
result := a
|
|
end;
|
|
|
|
function LCM(a, b: Int64): Int64;
|
|
begin
|
|
LCM := (a DIV GCD(a,b)) * b;
|
|
end;
|
|
|
|
procedure InitLCM(Base:NativeInt);
|
|
var
|
|
i : integer;
|
|
Begin
|
|
For i := Base to (Base*Base-1) do
|
|
LCMsHL[i] := LCM(i,Base);
|
|
end;
|
|
|
|
function CountGapFul(H_Digit,Base:NativeInt;PotBase:Uint64):Uint64;
|
|
//Counts gapfulnumbers [n*PotBase..(n+1)*PotBase -1] ala [100..199]
|
|
var
|
|
EndDgt,Dgt : NativeInt;
|
|
P,k,lmt,sum,dSum: UInt64;
|
|
begin
|
|
P := PotBase*H_Digit;
|
|
lmt := P+PotBase-1;
|
|
Dgt := H_Digit*Base;
|
|
sum := (PotBase-1) DIV dgt +1;
|
|
For EndDgt := 1 to Base-1 do
|
|
Begin
|
|
inc(Dgt);
|
|
//search start
|
|
//first value divisible by dgt
|
|
k := p-(p MOD dgt)+ dgt;
|
|
//value divisible by dgt ending in the right digit
|
|
while (k mod Base) <> EndDgt do
|
|
inc(k,dgt);
|
|
IF k> lmt then
|
|
continue;
|
|
//one found +1
|
|
//count the occurences in (lmt-k)
|
|
dSum := (lmt-k) DIV LCMsHL[dgt] +1;
|
|
inc(sum,dSum);
|
|
//writeln(dgt:5,k:21,dSum:21,Sum:21);
|
|
end;
|
|
//writeln(p:21,Sum:21);
|
|
CountGapFul := sum;
|
|
end;
|
|
|
|
procedure Main(Base:NativeUInt);
|
|
var
|
|
i : NativeUInt;
|
|
pot,total,lmt: Uint64;//High(Uint64) = 2^64-1
|
|
Begin
|
|
lmt := High(pot) DIV Base;
|
|
pot := sqr(Base);//"100" in Base
|
|
setlength(LCMsHL,pot);
|
|
InitLCM(Base);
|
|
total := 0;
|
|
repeat
|
|
IF pot > lmt then
|
|
break;
|
|
For i := 1 to Base-1 do //ala 100..199 ,200..299,300..399,..,900..999
|
|
inc(total,CountGapFul(i,base,pot));
|
|
pot *= Base;
|
|
writeln('Total [',sqr(Base),'..',Numb2USA(IntToStr(pot)),'] : ',Numb2USA(IntToStr(total+1)));
|
|
until false;
|
|
setlength(LCMsHL,0);
|
|
end;
|
|
|
|
BEGIN
|
|
Main(10);
|
|
Main(100);
|
|
END.
|