Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
Trả lời: Tốn thời gian :( (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 0
CHỦ ĐỀ - Trả lời: Tốn thời gian :(
#59190
AngelStudy (Thành viên)
Đang tập code
Bài viết: 2
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Tốn thời gian :( 9 năm trước   (+0)
Bài 1: phân số p/q(p,q là 2 số nguyên dương) gọi là phân số đúng nếu p/q nhỏ hơn 1, còn p/q gọi là phân số tối giản nếu UCLN(p,q)=1.
Yêu cầu:
+Cho trước số nguyên n(3<=n<=50000000)
a, tính số lượng các phân số đúng, tối giản p/q mà p+q=n.
b, tìm phân số đúng, tối giản p/q lớn nhất mà p+q=n.
vd
Input
18
Output
3
7 11

Code của em
Code:
var i,j,n,p,q,s,m,t:longint;
      function Test(a,b:longint):boolean;
           begin
                test:=false;
              if a=1 then
                 begin
                   test:=true;
                    exit;
                   end
                else
                if (b mod a=0) then exit
                    else
                         begin
                               while a<>b do
                                   begin
                                      if a>b then a:=a-b;
                                      if a<b then b:=b-a;
                                   end;
                         if a=1 then test:=true;
                end;
                        end;
begin
          
            write('Nhap n: ');
            readln(n);
m:=n div 2; t:=n;
for i:=1 to m do
 begin
  if i mod 2=0 then j:=i+1
    else
      j:=i;
  while j<n do
    begin
      if i+j=n then
           if test(i,j) then
      begin
        s:=s+1;
        p:=i;
        q:=j;
      end;
    j:=j+2;
    end;
    t:=n-i-1;
   end;
 
   writeln(s);
   write(p,'/',q);
readln
end.
bài em chạy hơn 5s từ n>50000 mà yêu cầu là 50000000 Mấy anh có cách nào khác để code chạy bé hơn 2s không ạ em xin cảm ơn
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#59193
version1001 (Thành viên)
version1001+5
Biết code binary-indexed tree
Bài viết: 32
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Tốn thời gian :( 9 năm trước   (+0)
AngelStudy viết:
QUOTE:
Bài 1: phân số p/q(p,q là 2 số nguyên dương) gọi là phân số đúng nếu p/q nhỏ hơn 1, còn p/q gọi là phân số tối giản nếu UCLN(p,q)=1.
Yêu cầu:
+Cho trước số nguyên n(3<=n<=50000000)
a, tính số lượng các phân số đúng, tối giản p/q mà p+q=n.
b, tìm phân số đúng, tối giản p/q lớn nhất mà p+q=n.
vd
Input
18
Output
3
7 11

Mình nghĩ bạn nên dùng thuật toán Euclid để tìm ước chung lớn nhất của hai số sẽ nhanh hơn. Đây là chương trình cải tiến để bạn tham khảo, chạy với n=10000000 trong 2s:
Code:
program phanso;
var n,p,q,kq:longint;
{*=======================================================*}
procedure nhap;
        begin
             read(n);
        end;
{*=======================================================*}
function UCLN(a,b:longint):longint;
        begin
             if (a mod b)=0 then UCLN:=b
             else UCLN:=UCLN(b, a mod b);
        end;
{*=======================================================*}
procedure xuly;
var m,i,u,v:longint;
        begin
             m:=n div 2;
             if n div 2=0 then m:=m-1;
             p:=0;
             q:=1;
             kq:=0;
             for i:=1 to m do
                begin
                     u:=i;
                     v:=n-i;
                     if UCLN(u,v)=1 then
                        begin
                             inc(kq);
                             if (p/q) < (u/v) then
                                begin
                                     p:=u;
                                     q:=v;
                                end;
                        end;
                end;
        end;
{*=======================================================*}
procedure xuat;
        begin
             writeln(kq);
             write(p,'/',q);
        end;
{*=======================================================*}
begin
        nhap;
        xuly;
        xuat;
end.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#59195
Nguyen_Duy_Khanh (Thành viên)
songuku95+25
Không code nữa rồi
Bài viết: 374
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Tốn thời gian :( 9 năm trước   (+0)
2 số a,b có UCLN (a,b)=1 và a+b=k thì UCLN (a,k) = UCLN (b,k) = 1
=> số các số (a,b) là phi(k)
 
Đã lưu IP Đã lưu IP  
 
Y!M: duy_khanh308
  Đã khóa chức năng gửi bài.
#59196
unknown (Thành viên)
Đã biết code đệ quy
Bài viết: 16
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Tốn thời gian :( 9 năm trước   (+0)
Nguyen_Duy_Khanh viết:
QUOTE:
2 số a,b có UCLN (a,b)=1 và a+b=k thì UCLN (a,k) = UCLN (b,k) = 1
=> số các số (a,b) là phi(k)

bạn có thể nói rõ hơn về phi(k) đc ko,
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#59197
flashmt (Admin)
flash_mt+99
Admin
Bài viết: 417
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Tốn thời gian :( 9 năm trước   (+0)
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#59198
AngelStudy (Thành viên)
Đang tập code
Bài viết: 2
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Tốn thời gian :( 9 năm trước   (+0)
version1001 viết:
QUOTE:
AngelStudy viết:
QUOTE:
Bài 1: phân số p/q(p,q là 2 số nguyên dương) gọi là phân số đúng nếu p/q nhỏ hơn 1, còn p/q gọi là phân số tối giản nếu UCLN(p,q)=1.
Yêu cầu:
+Cho trước số nguyên n(3<=n<=50000000)
a, tính số lượng các phân số đúng, tối giản p/q mà p+q=n.
b, tìm phân số đúng, tối giản p/q lớn nhất mà p+q=n.
vd
Input
18
Output
3
7 11

Mình nghĩ bạn nên dùng thuật toán Euclid để tìm ước chung lớn nhất của hai số sẽ nhanh hơn. Đây là chương trình cải tiến để bạn tham khảo, chạy với n=10000000 trong 2s:
Code:
program phanso;
var n,p,q,kq:longint;
{*=======================================================*}
procedure nhap;
        begin
             read(n);
        end;
{*=======================================================*}
function UCLN(a,b:longint):longint;
        begin
             if (a mod b)=0 then UCLN:=b
             else UCLN:=UCLN(b, a mod b);
        end;
{*=======================================================*}
procedure xuly;
var m,i,u,v:longint;
        begin
             m:=n div 2;
             if n div 2=0 then m:=m-1;
             p:=0;
             q:=1;
             kq:=0;
             for i:=1 to m do
                begin
                     u:=i;
                     v:=n-i;
                     if UCLN(u,v)=1 then
                        begin
                             inc(kq);
                             if (p/q) < (u/v) then
                                begin
                                     p:=u;
                                     q:=v;
                                end;
                        end;
                end;
        end;
{*=======================================================*}
procedure xuat;
        begin
             writeln(kq);
             write(p,'/',q);
        end;
{*=======================================================*}
begin
        nhap;
        xuly;
        xuat;
end.
Thank anh ! em biết code của em bị chậm chỗ nào rồi'' em làm thừa vòng lặp quá ''
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS