mong các bạn giúp mình bài này:

[hai6f2009]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Đất nước Văn Lang thời cổ xưa đã có những hiểu biết tân tiến về số học. Tương truyền rằng, vua Hùng Vương thứ 17 cùng các trưởng lão trong triều đình đã phát minh ra các số huyền bí. Các số này giúp chỉ dẫn đường vào kho tàng của đất nước.
Theo các chứng tích khảo cổ, các nhà khoa học kết luận rằng số huyền bí cơ sở a bằng tích của (3^d-1) với mọi ước số d > 0 của a.
Bờm thích số học đồng thời cũng rất thích tìm hiểu lịch sử đất nước. Bạn hãy giúp Bờm tính số huyền bí cơ sở a (1 ≤ a ≤ 109). Do kết quả có thể rất lớn, bạn chỉ cần in ra phần dư của số huyền bí cơ sở a khi chia cho 20122007.
Dữ liệu

Gồm một số nguyên a duy nhất.
Kết qủa

In ra số nguyên duy nhất là phần dư của số huyền bí cơ sở a khi chia cho 20122007.
Ví dụ

Dữ liệu: 10 Kết qủa 7291779

 

[hgminh95]

bạn copy đề thì cũng nên chỉnh sửa lại chút chứ nhỉ :|
(3d-1) -> 3^d - 1
1 ≤ a ≤ 109 -> 1<= a <= 10^9

bài này thuật cũng ko có gì, chỉ là tìm các ước của a rồi tính thôi

 

[hai6f2009]

là sao vậy bạn? tức là mình chỉ tìm ước của nó rồi đem nhân như bài rồi chia cho 20120007 phải không bạn?

 

[hgminh95]

là sao vậy bạn? tức là mình chỉ tìm ước của nó rồi đem nhân như bài rồi chia cho 20120007 phải không bạn?

đúng đó bạn
nhưng chú ý trong đoạn tìm ước để giảm đpt thì nếu i là ước thì n div i cũng là ước (nếu n div i <> i), cái này để giảm đoạn tìm ước chỉ cần duyệt đến trunc(sqrt(n))
ngoài ra thì khi tính a^b bạn tính với đpt log b nữa là ac

đoạn tính mod bạn cũng lưu ý là vừa tính vừa mod chứ ko tính ra được cái tích (3^d + 1) đâu vì nó quá lớn

 

[hai6f2009]

???

đúng đó bạn
nhưng chú ý trong đoạn tìm ước để giảm đpt thì nếu i là ước thì n div i cũng là ước (nếu n div i <> i), cái này để giảm đoạn tìm ước chỉ cần duyệt đến trunc(sqrt(n))
ngoài ra thì khi tính a^b bạn tính với đpt log b nữa là ac

đoạn tính mod bạn cũng lưu ý là vừa tính vừa mod chứ ko tính ra được cái tích (3^d + 1) đâu vì nó quá lớn

Bạn ơi, mấy chỗ bạn viết tắt là sao vậy bạn? Mình đọc mà không hiểu lắm.

 

[11thanhkhoeo]

vấn đề ở đây là xử lí số lớn Các chú xem ở bên topic thuật toán nhé

Thân

 

[hgminh95]

mấy chỗ viết tắt là độ phức tạp

@11thanhkhoeo: bài này chỉ cần in ra phần dư nên cũng không cần xử lý số lớn, có thể dựa vào ct này:
(a * b) mod c = ((a mod c) * (b mod c)) mod c (phép + cũng tương tự:

đây là code của mình

const
  fi='';
  fo='';
  d=20122007;
var
  f:text;
  n:longint;
  kq:int64;
function power(x,p:int64):int64;
var
   u:int64;
begin
    if p=1 then exit(x);
    u:=power(x,p div 2);
    if odd(p) then power:=(u*u*x) mod D
    else power:=(u*u) mod D;
end;
procedure xuli;
var
  i,k:longint;
begin
  kq:=1;
  for i:=1 to trunc(sqrt(N)) do
    if n mod i=0 then
      begin
        kq:=(kq*(power(3,i)-1) mod D) mod D;
        if i <> n div i then kq:=(kq*(power(3,n div i)-1) mod D) mod D;
      end;
end;
begin
  assign(f,fi);reset(f);
    readln(f,N);
  close(f);
  assign(f,fo);rewrite(f);
    if n=1 then write(f,2) else
    begin
      xuli;
      write(f,kq);
    end;
  close(f);
end.

 

[hai6f2009]

Cảm ơn bạn rất nhiều! Nhưng bạn ơi, code của bạn chạy với đpt bao nhiêu vậy bạn?

 

[hgminh95]

đpt vào khoảng sqrt(n)*log d, đủ để ac bài này
...@@...

 

[hai6f2009]

còn đây là bài thứ 2:
Từ tập các bài có trên SPOJ (oi)
8164. VOI 2011 Phần thưởng
Mã bài: BONUS

Tuấn là người chiến thắng trong một cuộc thi “tìm hiểu kiến thức vũ trụ” và được nhận các phần thưởng do công ty XYZ tài trợ. Các phần thưởng được bố trí trên một bảng hình vuông nxn có dạng một lưới ô vuông kích thước đơn vị. Các dòng của bảng được đánh số từ 1 đến n, từ trên xuống dưới và các cột của bảng được đánh số từ 1 đến n, từ trái qua phải. Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j) và trên ô đó chứa một món quà có giá trị là a[i,j] (1 <= i, j <= n)

Đề nhận phần thưởng, Tuấn được phép chọn một hình vuông kích thước k x k chiếm trọn trong một số ô của bảng và nhận tất cả các phần quà có trong các ô nằm trong hình vuông đó.

Yêu cầu: Hãy xác định tổng giá trị lớn nhất của món quà mà Tuấn có thể nhận được.

Dữ liệu:

Dòng thứ nhất chứa hai sô nguyên dương n, k (n <= 1000, n/3 <= k <= n).
Dòng thứ i trong số n dòng tiếp theo chứa n số nguyên dương, số thứ j là a[i,j] (a[i,j] <= 1000)

Kết quả: Ghi ra một số nguyên duy nhất là tổng giá trị lớn nhất của các món quà mà Tuấn có thể nhận được.

Ví dụ:

Dữ liệu


Kết quả

4 3
1 9 1 1
9 9 9 9
1 9 9 9
1 9 9 14



86








1


9


1


1

9


9


9


9

1


9


9


9

1


9


9


14







Ràng buộc: 50% số test ứng với 50% số điểm của bài có n <= 100.