SỐ HUYỀN BÍ – MYSTERY – SPOJ | LÀM HẾT MÌNH

Trang chủ » Số Huyền Bí Pascal » SỐ HUYỀN BÍ – MYSTERY – SPOJ | LÀM HẾT MÌNH

Có thể bạn quan tâm

LÀM HẾT MÌNH – VÌ CHÍNH MÌNH Bỏ qua nội dung ← KHỐI LẬP PHƯƠNG LỚN NHẤT – MAXCUB – SPOJ VÒNG SỐ NGUYÊN TỐ – PCIRCLE – SPOJ →

SỐ HUYỀN BÍ – MYSTERY – SPOJ

Đăng trong 11/06/2014 bởi connhangheovodanh

ĐỀ BÀI :

SỐ HUYỀN BÍ – MYSTERY – SPOJ

Đấ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 (3d-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

THUẬT TOÁN :

Ta có một số nhận xét như sau. Để tính được nghiệm của bài toán thì chỉ cần for 1 vòng từ     1 ->  √n  rồi tính 3^i-1 và 3^(n/i)-1 nhân lại rồi nhân vào res thôi. Chú ý khi nó là số chính phương thì căn của nó chỉ tính 1 lần thôi nha! Khi đó thực hiện trong O(sqrt(N))

Bây giờ là tính 3^i -1 bằng cách nào. Nếu vét thì trường hợp xấu nhất là O(10^9) chết ngắt. Nhận xét 3^9 = 3^4 x 3^4 x 3 mà 3^4 = 3^2 x 3^2 … dùng đệ qui bình thường trong thời gian log2(i) thôi mà log2(10^9) = 29 (nhỏ xíu như hạt đậu ấy).

Vậy khi đó tổng thời gian thuật toán không quá O(sqrt(N)*log2(N)) < 10^6 dư sức chạy.

Chú ý một điều (3^d-1) mod base = ((3^d mod base) – 1) mod base nên ta yên tâm tính 3^d trước rồi mới tính 3^d-1.

CODE :

#include <iostream> #include <fstream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath>   #define ll              long long   using namespace std;   const int   base = 20122007; ll          n,res = 1;   ll  g(int x) {     if (x == 1) return 3;     ll tmp = g(x/2) % base;     if (x % 2 == 0) return (tmp*tmp) % base;     return ((tmp*tmp % base)*3) % base; }   ll  f(int x) {     return (g(x) - 1 + base) % base; }   int main() {     scanf("%lli",&n);     for (int i=1;i*i<=n;i++) {         if (n % i == 0) {             if (i*i == n)                 res = res*f(i) % base;             else                 res = ((res*f(i) % base) * f(n/i)) % base;         }     }     printf("%lli",res);     return 0; }

Chia sẻ:

  • X
  • Facebook
Thích Đang tải...

Có liên quan

Bài này đã được đăng trong Spoj. Đánh dấu đường dẫn tĩnh. ← KHỐI LẬP PHƯƠNG LỚN NHẤT – MAXCUB – SPOJ VÒNG SỐ NGUYÊN TỐ – PCIRCLE – SPOJ →

1 Response to SỐ HUYỀN BÍ – MYSTERY – SPOJ

  1. Hình đại diện của Không hiểu Ẩn danh nói: 11/06/2014 lúc 9:24 Chiều

    page này hay đó

Bình luận về bài viết này

Δ

  • Tìm kiếm cho:

  • Thống kê

    • 291 004 lượt xem

  • Bài viết mới

    • SPOJ – Tin mật – SEC 02/04/2015
    • SPOJ – Chuỗi từ – CHAIN2 30/03/2015
    • SPOJ – ACM – ACMNB 27/03/2015
    • SPOJ – Chuỗi ốc – BEADSNB 27/03/2015
    • Codeforces – Tutorial For Contest Nowruz challenge 25/01/2015
    • SPOJ – Phần tử thứ K – YPKTH 24/01/2015
    • SPOJ – Cuộc đấu cân não – NCOB 20/01/2015
    • SPOJ – Time Travel – TTRAVEL 20/01/2015
    • SPOJ – Tập hợp động – CPPSET (cơ bản về set) 20/01/2015
    • SPOJ – Dãy số may mắn – NKLUCK 15/01/2015
    • SPOJ – Above the Median – KMEDIAN 13/01/2015
    • SPOJ – LUBENICA – LUBENICA 11/01/2015
    • SPOJ – Lowest Common Ancestor – LCA 11/01/2015
    • SPOJ – Tăng tốc mạng máy tính – NETACCEL 11/01/2015
    • SPOJ – Floyd hoặc Dijkstra ( Cơ bản ) – FLOYD 11/01/2015

  • Follow

    Enter your email address to follow this blog and receive notifications of new posts by email.

    Địa chỉ email:

    Theo dõi

    Tham gia cùng 26 người đăng ký khác

  • Lượt nhấp chuột hàng đầu

    • ideone.com/PQN4Dl
    • vn.spoj.com/problems/SEC
  • Tìm kiếm cho:

  • Liên kết

    • Tạo tài khoản
    • Đăng nhập
    • RSS bài viết
    • RSS bình luận
    • WordPress.com
LÀM HẾT MÌNH – VÌ CHÍNH MÌNH Blog tại WordPress.com.
  • Bình luận
  • Đăng lại
  • Theo dõi Đã theo dõi
    • LÀM HẾT MÌNH - VÌ CHÍNH MÌNH
      • Đã có 26 người theo dõi Theo dõi ngay
    • Đã có tài khoản WordPress.com? Đăng nhập.
    • LÀM HẾT MÌNH - VÌ CHÍNH MÌNH
    • Theo dõi Đã theo dõi
    • Đăng ký
    • Đăng nhập
    • URL rút gọn
    • Báo cáo nội dung
    • Xem toàn bộ bài viết
    • Quản lý theo dõi
    • Ẩn menu
%d Tạo trang giống vầy với WordPress.comHãy bắt đầu

Từ khóa » Số Huyền Bí Pascal