SQUARES - Hình vuông

Tác giả: ll931110

Ngôn ngữ: Pascal

Program SQUARES;
  Const
    input  = '';
    output = '';
    maxn = 1000000;
  Var
    a,F: array[1..maxn] of longint;
    t,n,i: longint;
    fi,fo: text;

Procedure openfile;
  Begin
    Assign(fi, input);
      Reset(fi);

    Assign(fo, output);
      Rewrite(fo);
  End;

Procedure solve;
  Var
    i,j,k,tmp,res: longint;
  Begin
    Fillchar(a, sizeof(a), 0);
    For i:= 2 to trunc(sqrt(maxn)) do
      if a[i] = 0 then
      Begin
        k:= 2 * i;
        While k <= maxn do
          Begin
            a[k]:= i;
            k:= k + i;
          End;
      End;

    F[1]:= 1;
    For i:= 2 to maxn do
      if a[i] = 0 then F[i]:= i - 1 else
        Begin
          k:= 0;
          tmp:= i;

          While tmp mod a[i] = 0 do
            Begin
               inc(k);
               tmp:= tmp div a[i];
            End;

          If tmp = 1 then
            Begin
              F[i]:= a[i] - 1;
              For j:= 1 to k - 1 do F[i]:= F[i] * a[i];
            End
          else F[i]:= F[tmp] * F[i div tmp];
        End;

      Readln(fi, n);
      res:= 0;
      For i:= 1 to n - 1 do
        if n mod i = 0 then res:= res + F[n div i + 1] div 2;

      Writeln(fo, res + 1);
  End;

Procedure closefile;
  Begin
    Close(fo);
    Close(fi);
  End;

Begin
  openfile;
  solve;
  closefile;
End.

Download