Tìm số dư của lũy thừa số rất lớn

Các bạn ace trên diễn đàn có thể chỉ giúp mình hướng làm bài này với được không ạ. Mình cám ơn.
Hãy tính giá trị biểu thức (1^n + 2^n + 3^n + 4^n) mod 5
Input:
Dòng đầu là số lượng bộ test T (T ≤ 100).
Mỗi test gồm một xâu biểu diễn số nguyên n, n có không quá 100 000 kí tự.
ví dụ : n=4 thì in ra 4

Mũ mod dễ mà, bài này có cả trick :smiley: áp dụng định lí Fermat nhỏ O(1) :slight_smile:

2 Likes

Nguồn đích thị spoj :smile:
Bài này không hề dùng mũ to nhé. Dùng toán thôi.
Gợi ý: xét n mod 4.

Bản chất thì cách của mình và cách của @rogp10 như nhau.

1 Like

Số modulo cho trước dễ cực kì :slight_smile:

2 Likes

Có bài này hay nè
Viết chương trình tính 2^6972593 - 1,
Có 1 Đai Ca nôi tiếng thê giới đã chiến thắng bài này trong năm 2000.

2 Likes

Tính đầy đủ hay chỉ tính mod thôi ạ?

2 Likes

đầy đủ. ấy, kết quả phép tính đó :v

1 Like

:"> Cái bài này của hacker Fabrice Bellard đây mà

4 Likes

Cám ơn bạn để mk xem thử

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?