01/10/2018, 15:51
Bị Time Limit Exceeded trên codefun
#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 ạ.
Bài liên quan
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.
Bạn có thể giúp mình sửa lỗi được không ạ
Bạn tự biến đổi f(n) với n chẵn và n lẻ xem nó ra cái gì.
N chẵn thì sẽ ra kq + còn lẻ thì ra kq âm
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.Bài này dùng biến đổi đại số O(1) :v
MÌnh vẫn chưa hiểu ý bạn cho lắm (sorry, mình mới học).
Do tổng có dạng (-1)^n*a[n] nên dùng ct tính tổng lẻ và tổng chẵn đã. Rồi xem chẵn hay lẻ mang dấu trừ. Sau đó bạn tính ra ct và viết vào thôi.
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.