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 | 
 

 Phương trình nghiệm nguyên

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 đề: Phương trình nghiệm nguyên   Tue 27 Jul 2010, 13:27

Cho phương trình có dạng: x*x+y*y=r*r.

với r nguyên dương (R<=100000)

Hãy tìm số lượng nghiệm của phương trình đó
Input

Gồm một số r duy nhất
Output

Gồm một số duy nhất là đáp số của bài toán.
Example

Input 1:
1

Output 1:
4

Input 2:
3

Output 2:
4

Input 3:
10

Output 3:
12
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: Phương trình nghiệm nguyên   Wed 28 Jul 2010, 11:06

Cái ni dùng toán học hoặc chạy thoe kiểu tin đều được. Chỉ có 1 chú ý là nghiệm nguyên nên nếu (x,y) là 1 nghiệm thì (x,-y);(-x,y);(-x,-y) đều là nghiệm

_________________
Đờ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: Phương trình nghiệm nguyên   Wed 28 Jul 2010, 15:41

Cái này dùng 2 vòng for thì chỉ chạy được các test nhỏ thôi.
=>Các test lớn thì đợi khoảng hơn 2 tiếng thôi=>Chưa tối ưu.

_________________
P.T.H.T
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: Phương trình nghiệm nguyên   Thu 29 Jul 2010, 18:06

Anh nghĩ em chạy 2 vòng for à. Em chạy có 1 vòng mà

for x:=1 to r-1 do if sqrt(r^2 - x^2)=trunc(sqrt(r^2 - x^2)) then dem:=dem+4;

_________________
Đờ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: Phương trình nghiệm nguyên   Thu 29 Jul 2010, 22:31

Một vòng for cũng không đc.

_________________
P.T.H.T
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: Phương trình nghiệm nguyên   Fri 30 Jul 2010, 11:29

10^5 thôi mà anh. 1 vòng for thì chạy 10^5 lần lặp, trong mỗi lần, thực hiện 5 phép tính và cả điều kiện nữa dồn lại cỡ 10 lần tính. tổng cộng 10^6 chu kì máy. Có 1 giây mà.

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
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: Phương trình nghiệm nguyên   Fri 30 Jul 2010, 11:35

Với lại em nói rồi, neus tin hok được thì kết hợp thêm toán

x^2=(r-y)*(r+y)

=> cách phân tích ra thừa số nguyên tố của vế phải phải có số lượng ước nguyên tố chẵn. QHD đẻ đếm với nhận xét vế phải bé hơn r^2 và ước nguyên tố lớn nhất có thể luôn nhỏ hơn 2*r. Tìm các số nguyên tố từ 1-->2r.

Nói thì thế chứ em thấy có toán vô còn lâu hơn nữa rolling on the floor .

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
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: Phương trình nghiệm nguyên   Fri 30 Jul 2010, 11:53

Anh kêu em chạy 1 vòng for hok được à ^^.

Anh chạy thử chương trình sau

Code:
program tim_nghiem_nguyen;
uses crt;
var x,r,rt,xt,dem:longint;

begin
  clrscr;
  write('nhap r: ');readln(r);
  rt:=sqr(r); dem:=0;
  for x:=1 to trunc(sqrt(rt div 2)) do
    begin
      xt:=sqr(x);
      xt:=rt-xt;
      if sqrt(xt)=trunc(sqrt(xt)) then dem:=dem+4;
    end;
  writeln(2*dem);
readln;
end

Bài ni chạy 10^5 mất khoảng 1 giây, nhưng mấy test nhỏ hơn thì enter là ra lun

_________________
Đờ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: Phương trình nghiệm nguyên   Fri 30 Jul 2010, 14:22

Hình như bạn chưa đọc kĩ đề thì phải.
Bạn xem lại code mình đã đúng test ví dụ chưa?
Mình thử nháp bằng giấy thì thấy không đúng test nào.
Mấy code của em trên forum cũng sai nhiều.Ngay test đề bài cũng chưa đúng thì làm thế nào đúng các test khác.

_________________
P.T.H.T
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: Phương trình nghiệm nguyên   Fri 30 Jul 2010, 17:18

laughing Anh làm gì mà căng thế. Tại em cho khác 0 thôi. Anh sửa x lại là chạy từ 0 hoặc khi in kết quả cộng thêm 4, đảm bảo ko sai.

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




Bài gửiTiêu đề: Re: Phương trình nghiệm nguyên   Today at 18:48

Về Đầu Trang Go down
 
Phương trình nghiệm nguyên
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Rừng Mắm - Bình Nguyên Lộc
» [Trắc nghiệm] 7 câu hỏi của FBI ~ Kiểm tra mức độ tâm thần của bạn~
» Trắc nghiệm Seme-Uke phiên bản Tiếng Việt ~
» Nguyên liệu và dụng cụ đan len
» [Entry]Con búp bê tội nghiệp

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 :: Lớp chuyên tin-
Chuyển đến