Làm thế nào để bài tập sau chạy được dưới 1s với số k lên đến 10e18?

[doancong (Duy)]

Xin chỉ giáo giúp làm làm thế nào để bài tập sau chạy được dưới 1s với số k lên đến 10e18? Mình chỉ chạy được với k đến 10e12

Tính tổng TOTAL.*
Sau buổi học về số học, Minh đã biết cách tính tổng của n số tự nhiên liên tiếp. Ở nhà Minh tiếp tục làm các bài tập về tính tổng của các số tự nhiên liên tiếp. Minh thắc mắc, liệu với số tự nhiên K thì có thể phân tích K thành tổng của các số tự nhiên liên tiếp hay không? Ví dụ: với K=9 có thể phân tích : 9 = 9, 9 = 4 + 5, 9 = 2 + 3 + 4. Tức là có 3 cách phân tích thành tổng của các số tự nhiên liên tiếp.
Yêu cầu: Viết chương trình giúp Minh tìm số cách phân tích số tự nhiên K thành tổng các số tự nhiên liên tiếp.
Dữ liệu: Vào từ file văn bản TOTAL.INP gồm một dòng duy nhất chứa số nguyên dương K ( 1<=K<=1018).
Kết quả: Đưa ra file văn bản TOTAL.OUT một dòng duy nhất chứa số cách phân tích tìm được.
Ví dụ:
TOTAL.INP TOTAL.OUT
9 3

[kisuluoibieng (Tên Gì Cũng Được)]

Code chạy được đến 10e12 đâu?

[doancong (Duy)]

#include <bits/stdc++.h>

using namespace std;
long long n,k,dem=1;
int main()
{
    freopen("TOTAL.inp","r",stdin);
    freopen("TOTAL.out","w",stdout);
    cin>>n;
    if(n%2==0)k=2; else k=1;
    for(;k<sqrt(8*n);k++)
    if(2*n%(k+1)==0&&((2*n)/(k+1)-k)%2==0&&((2*n)/(k+1)-k)>0){dem++;}
    cout<<dem;
    return 0;
}

[kisuluoibieng (Tên Gì Cũng Được)]

bạn hãy sửa format lại, giải thích về ý tưởng của bạn

[doancong (Duy)]

tổng các số: a +(a+1) + (a+2) + … +(a+k) = (2a+k)(k+1) = n
suy ra a= (n/(k+1) - k )/2. và k<sqrt(8n)
nên duyệt các số k từ 1 đến sqrt(8n) để tìm a, nếu a nguyên dương thì được 1 cách.

[noname00 (HK boy)]

@doancong

tổng các số: a +(a+1) + (a+2) + … +(a+k) = (2a+k)(k+1) = n
suy ra a= (n/(k+1) - k )/2. và k<sqrt(8n)

Đúng ra thì a + (a+1) + (a+2) + ... + (a+k) = (2a+k)(k+1)/2 = n

Bạn có thể phân tích k+1 <= sqrt(2n) mà

[doancong (Duy)]

@doancong

if(n%2==0)k=2; else k=1;

đúng…
nhưng vẫn ko thể chạy được lên đến 10e18

[kisuluoibieng (Tên Gì Cũng Được)]

với số n có thể phân tích bằng tổng của k số liên tục (a, a+1, …, a+k-1)
ta có biểu thức sau

n = a + (a+1) + … + (a+k-1)
n = ak + 1 + 2 + … + (k-1) // chỉ là gom k số a lại thôi
n = ak + k*(k-1)/2
2n = 2ak + k^2 - k
k^2 + (2a - 1)k - 2n = 0

ồ, tới đây mình có một cái phương trình bậc 2 với biến là k
để thoã được cái câu in đậm phía trên, thì chúng ta sẽ tìm tất cả cặp a, k (a >=0, k >=1) nguyên thoã mãn phương trình.
hay nói cách khác là tìm tất cả số a >= 0 để phương trình trên có nghiệm nguyên dương, và đó cũng là đáp án (cũng dễ nhận thấy là với một số a thì cũng chỉ có tối đa một số k thoã mãn đề bài thôi)

giải phương trình thôi

dt = (2a-1)^2 + 8n, (dt này chắc chắn > 0, nên có 2 nghiệm)
dt =
k1 = (1 - 2a + sqrt(dt)) / 2a
k2 = (1 - 2a - sqrt(dt)) / 2a, loại k2 vì nghiệm này k2 âm

nhìn vào chỉ có k1 = (1 - 2a + sqrt((2a-1)^2 + 8n)) / 2a
tới đây thì có thể phân tích thêm để giảm bớt scope của a và lặp theo a
hoặc lại quy về một phương trình bậc 2 hoặc …, nhưng đại loại là bài toán sẽ quy về tìm tất cả không âm sao cho biểu thức ở trên nguyên

mình nghĩ vu vơ tới đây thôi, bạn có thể tự phân tích thêm

[tntxtnt]

ta có

• 9 = (1+2+3+…+9) - (1+2+3+…+8) = 9(9+1)/2 - 8(8+1)/2
• 4+5 = (1+2+3+4+5) - (1+2+3) = 5(5+1)/2 - 3(3+1)/2
• 2+3+4 = (1+2+3+4) - (1) = 4(4+1)/2 - 1(1+1)/2

vậy số n có thể phân tích thành n = a(a+1)/2 - b(b+1)/2

hay 2n = a^2 + a - b^2 - b = a^2 - b^2 + (a - b) = (a - b)(a + b + 1)

vậy chỉ cần đếm số cách phân tích 2n thành tích 2 số x y là ra có bao nhiêu cách phân tích n thành tổng các số tự nhiên liên tiếp :V

vd ở trên:

• với 9: a = 9, b = 8, a-b = 1, a+b+1 = 18, 1*18 = 2*9 = 2n
• với 4+5: a = 5, b = 3, a-b = 2, a+b+1 = 9, 2*9 = 2*9 = 2n
• với 2+3+4: a = 4, b = 1, a-b = 3, a+b+1 = 6, 3*6 = 2*9 = 2n

có thể còn có corner case là pt
a - b = x
a + b + 1 = y
có thể vô nghiệm hoặc ko có nghiệm a, b nguyên với cặp x y nào đó? Phân tích được 2n thành x*y rồi thì có thể phải giải pt 2 ẩn này nữa, mà giải cũng dễ thôi :V
2a + 1 = x + y
b = a - x
a = (x + y - 1) / 2
b = (-x + y - 1) / 2
kiểm tra a, b là nghiệm nguyên a > 0, b >= 0 nữa là xong :V

nhìn qua thì thấy cần x+y là số lẻ để có nghiệm nguyên, cần y > x để b >= 0, vậy chỉ cần chạy x từ 1 tới căn(2n) để xét 2n có chia hết cho x ko, nếu chia hết thì kiểm tiếp x+y = x + 2n/x phải là số lẻ nữa là xong.

chạy thử số nhỏ ra được dãy 1 2 1 2 2 2 1 3 2 2 2 2 2 4, tìm trên oeis ra https://oeis.org/search?q=1+1+2+1+2+2+2+1+3+2+2+2+2+2+4+1+2&sort=&language=english&go=Search A001227 Number of odd divisors of n. Cũng có lý. 2n là số chẵn nên 2n = xy thì 1 trong 2 hoặc cả x và y là số chẵn. Mà ở đây ta muốn x+y lẻ nên x hoặc y phải là số lẻ, vậy bài toán quy về đếm số ước lẻ của 2n :V

phân tích 2n thành thừa số nguyên tố 2n = 2^{e_0} * p_1^{e_1} * p_2^{e_2} * p_3^{e_3} * ... * p_w^{e_w} với p_i là số nguyên tố khác 2. Đáp án là tích (e_1 + 1)(e_2 + 1)(e_3 + 1)...(e_w + 1)

vậy trường hợp tệ nhất của bài toán giống như kiểm tra 1 số 18 chữ số có phải là số nguyên tố hay ko

Fastest way to prime factorise a number up to 10^18

tìm m sao cho n = 2^{e'_0} * m. Với m cỡ 1e18:

• dùng Miller-Rabin để ktra m là số ng tố hay ko, nếu ng tố thì đáp án là 2
• tạo sàng tới 1e6 và chia m cho các số ng tố trong sàng này
• nếu m ko chia hết cho số nt tố nào trong sàng thì bảo đảm m chỉ có tối đa 2 thừa số nguyên tố hay m = pq. Vậy đáp án là 4 nếu p khác q, hoặc 3 nếu p = q hay m là số chính phương.