Đề THT Toàn Quốc Lần Thứ XIX - 2013

T

thienvamai

bài 1 hình như có công thức thì phải
bài 2 chắc phải dùng phi hàm Euler

sao để thcs gì mà khó vậy
 
L

lamdetien36

thienvamai said:
bài 1 hình như có công thức thì phải
bài 2 chắc phải dùng phi hàm Euler

sao để thcs gì mà khó vậy
Bấm để xem đầy đủ nội dung ...
Đề THT toàn quốc năm nay đó anh. Em mới thi rớt về đây nè :D
Anh giải hộ em bài 2, bài này khó dữ dội, em làm đk 7 test đầu, 8 test còn lại thì em chịu :(. Còn 2 bài kia thì dễ.
 
Last edited by a moderator:
M

mikelhpdatke

Bài 1 nếu xử lý thêm xâu nữa thì ăn được 10 test. Bài 2 mình làm được 10/15 test. Bài 3 thì repeat until + một số phương pháp sao cho đi nhanh, tùy vào từng người :))
 
L

lamdetien36

mikelhpdatke said:
Bài 1 nếu xử lý thêm xâu nữa thì ăn được 10 test. Bài 2 mình làm được 10/15 test. Bài 3 thì repeat until + một số phương pháp sao cho đi nhanh, tùy vào từng người :))
Bấm để xem đầy đủ nội dung ...
Bài 3 em chặt nhị phân ngu quá. Test = 2 chặt 88 lần :|
Về nhà chặt lại thì chưa có test nào vượt quá 125 lần :|
 
L

lamdetien36

Cuối cùng cũng tìm ra code bài 2. Đọc không hiểu gì hết luôn :|
Mã: 
{$MODE OBJFPC}
{$M 50000000}
program TetrationModulus;
const
  InputFile  = 'TETRATION.INP';
  OutputFile = 'TETRATION.OUT';
  maxN = Round(1E6);
  maxA = Round(1E6);
  maxM = Round(1E6);
var
  fi, fo: TextFile;
  a, n, m, res: Integer;
  d, phi: array[1..maxM] of Integer;

procedure Init;
var
  i, j, k: Integer;
begin
  //Sieve of Eratosthenes
  for i := 1 to m do d[i] := i;
  for i := 2 to Round(Sqrt(m)) do
    if d[i] = i then
      begin
        for j := i to m div i do
          if d[j * i] > i then
            d[j * i] := i;
      end;
  //Euler phi function
  phi[1] := 1;
  for i := 2 to m do
    begin
      j := i;
      k := d[j];
      while j mod k = 0 do
        begin
          j := j div k;
        end;
      phi[i] := phi[j] * (i div j - i div j div k);
    end;
end;

//check if a^exp > maxM
function Overflow(a, exp: Integer): Boolean;
begin
  Result := ln(a) * exp > ln(maxM);
end;

function Power(a, exp: Integer): Integer;
begin
  if exp = 0 then Exit(1);
  Result := Sqr(Power(a, exp div 2));
  if Odd(exp) then Result := Result * a;
end;

function PowerMod(a, exp, m: Integer): Integer;
begin
  if exp = 0 then Exit(1 mod m);
  Result := PowerMod(a, exp div 2, m);
  Result := Int64(Result) * Result mod m;
  if Odd(exp) then Result := Int64(Result) * a mod m;
end;

{
tra ve Result  a^^n mod m:
Result == a^^n neu a^^n <= maxM,
Result == gia tri nho > maxM dong du theo mod m
}

function PowerTower(a, n, m: Integer): Integer;
var
  exp: Integer;
begin
  if n = 0 then Exit(1);
  exp := PowerTower(a, n - 1, phi[m]);
  if not Overflow(a, exp) then
    Result := Power(a, exp)
  else
    begin
      Result := PowerMod(a, exp, m);
      Result := Result + maxM div m * m + m; //Cong them cho > maxM
    end;
end;

procedure Solve;
begin
  while not SeekEof(fi) do
    begin
      ReadLn(fi, a, n, m);
      Init;
      res := PowerTower(a, n, m);
      res := res mod m;
      WriteLn(fo, res);
    end;
end;

begin
  AssignFile(fi, InputFile); Reset(fi);
  AssignFile(fo, OutputFile); Rewrite(fo);
  try
    Solve;
  finally
    CloseFile(fi); CloseFile(fo);
  end;
end.
Rốt cuộc em vẫn không hiểu phi là cái quái gì nữa :(
 
E

englandhuynh

B3 làm giống tìm kiếm nhị phân , thêm mấy cái giới hạn là được. tốt với n lớn và nguợc lại với n bé
 
M

megamanxza

Bái phục sự siêng năng và tài gõ nhanh của các bác! Em mới về, tắm rửa xong lên online là thấy chình ình trước mắt! =))
Chúc mừng bác Lâm, Đạt và Anh!!! Bravo!!!
Bài 1 em làm được 9 test, bài 2 em làm được 8 test còn bài 3 thì bỏ không! =))
 
T

thiennu274

@@ Mấy bạn chia sẻ thuật toán từng bài đi!!! :D
Mới đọc cái đề xong. Hình như bài 1 nó có quy luật ấy nhỉ, mình nghĩ là tính bình phương, giai thừa :)). Mà chắc là đi toi @@ vì thời gian lâu
Còn bài 2 thì... :D
 
L

lamdetien36

thiennu274 said:
@@ Mấy bạn chia sẻ thuật toán từng bài đi!!! :D
Mới đọc cái đề xong. Hình như bài 1 nó có quy luật ấy nhỉ, mình nghĩ là tính bình phương, giai thừa :)). Mà chắc là đi toi @@ vì thời gian lâu
Còn bài 2 thì... :D
Bấm để xem đầy đủ nội dung ...
Bài 1 tính theo CT 1^2+2^2+..+N^2
Bài 2 thì phải tính hàm phi() gì đó, cái này em ko hiểu nổi :(
 
Last edited by a moderator:
You must log in or register to reply here.
Top Bottom