Bị Time Limit Exceeded trên codefun

c++

(Anh Đức Bùi) #1
#include  < bits/stdc++.h>
#include  < cmath>
using namespace std;
int main()
{
   long long n,f;
   f=0;
   cin>>n;
   for (long long i=1; i<=n; i++)
   {
       f=f+pow(-1,i)*i;
   }
   cout<<f;


}

Đề: Nhập n(n<10^18). Tính f(n)=-1+2-3+4-5+…+((-1)^n)*n. Nhờ anh em giúp đỡ. Em cảm ơn ạ.


(HK boy) #2

Bài này phải biến đổi công thức chứ chạy trâu từ 1 -> 10^18 làm sao được.

Chạy vòng for từ 1 -> 10^8 đã chết thời gian rồi chứ đừng nói gì đến 10^18.


(Anh Đức Bùi) #3

Bạn có thể giúp mình sửa lỗi được không ạ


(HK boy) #4

Bạn tự biến đổi f(n) với n chẵn và n lẻ xem nó ra cái gì.


(Anh Đức Bùi) #5

N chẵn thì sẽ ra kq + còn lẻ thì ra kq âm


(HK boy) #6

Cụ thể đi hơn nào. Bài này cần kết quả chính xác, không ai cần biết dấu má của f như thế nào.

Đã include <bits/stdc++.h> thì bỏ <cmath> đi nhé, vì <bits/stdc++.h> đã có cả <cmath> rồi.


(rogp10) #8

Bài này dùng biến đổi đại số O(1) :v


(Anh Đức Bùi) #9

MÌnh vẫn chưa hiểu ý bạn cho lắm (sorry, mình mới học).


(Quân) #11

cái này là kiến thức toán học thôi không có liên quan đến lập trình đâu, nếu k giỏi chứng minh quy nạp thì có thể dùng công thức tính cấp số cộng cho phần chẵn và phần lẻ, cộng lại là ra kết quả. Tốc độ chương trình sau khi tính bằng công thức mới gần như không đổi với n lớn nhỏ khác nhau.
Ngoài ra bạn có thể chịu khó tốn ít nơ ron tìm công thức quy nạp thì cũng tốt
Gợi ý:
ta thấy rằng tổng của 2 số đôi một liên tiếp nhau luôn bằng 1
-1 + 2 - 3 + 4 … => -1 + 2 = 1 và -3 + 4 = 1
=> n chẵn thì có n/2 cặp số, n lẻ thì có (n - 1) / 2 cặp số dư ra -n
=> từ 2 mệnh đề trên rút ra công thức thôi.


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