Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

 Mod 29

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Mod 29   Tue 27 Jul 2010, 13:19

Xét số nguyên dương X và gọi S là tổng tất cả các ước dương của 2004^X .

Cần tính phần dư của S cho 29. Ví dụ, với X=1, các ước dương của 2004^1 là 1, 2, 3, 4, 6, 12, 167, 334, 501, 668, 1002 và 2004. Do đó S = 4704 và số dư của S chia cho 29 là 6.

Input

Gồm nhiều bộ test, mỗi bộ là một số nguyên X (1 <= X <= 10000000).

Bộ test với X = 0 để kết thúc chương trình và không cần xử lý.

Sample Input
1
10000
0

Output

Với mỗi bộ test, in ra một kết quả của số dư S chia cho 29 trên 1 dòng.

Sample Input
6
10

Note: làm quen với công thức tính tổng các ước số của 1 số - cách tính a^x mod p, cách tính (a^x-1)/(a-1) mod p
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Mod 29   Wed 28 Jul 2010, 09:04

Bài ni phải áp dụng toán học, tính theo tin đơn thuần thì n=10 đã đợi tới già rồi.

2004=(2^2)*3*167 có 3*2*2=12 ước số.

=> 2004^X=2^(2*X)*3^X*167*X có (2*X+1)*(X+1)*(X+1) ước

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Mod 29   Wed 28 Jul 2010, 23:23

Mình làm rồi nhưng không biết sai test nào:
Code:

Var            N,i:Longint;
                A,B,C,Kq:longint;
Function        Power(X,Y:Longint):longint;
Begin
                If Y=0 then Exit(1)
                Else
                If Y mod 2<>0 then Exit((Power(X,Y-1)*X) Mod 29)
                Else          Exit((Sqr(Power(X,Y div 2))Mod 29) MOd 29);
End;

BEGIN
                While not seekeof do
                Begin
                        Kq:=0;
                        Readln(N);
                        If N=0 then Exit;
                        A:=Power(2,2*N+1)-1;
                        B:=Power(3,N+1)-1;
                        C:=Power(167,N+1)-1;
                        A:=A*B*C Mod 29;
                        For i:=1 to 29 do
                        IF (i*13) Mod 29=A then
                        Begin
                                Writeln(i);
                        End;
                End;
END.

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
Sponsored content




Bài gửiTiêu đề: Re: Mod 29   Today at 18:46

Về Đầu Trang Go down
 
Mod 29
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Tin học căn bản-
Chuyển đến