Thảo luận thuật toán tối ưu cho bài toán Ramanujan và Euler

Ý tưởng là a^3 < n -> a <= pow(n, 1/3)
chọn b khi đã chọn a thì b <= pow(n- a^3, 1/3)

a từ 1 -> pow(n, 1/3), lặp tiếp b từ 1-> pow(n- a^3, 1/3),
c từ 1-> pow(n, 1/3), d từ 1-> pow(n- c^3, 1/3).

Còn bạn lặp 4 vòng for O(n^4) mà n=10000 thì timeout là đúng rồi

Chọn a, b, c tính d. O(n). 4 vòng lặp là dở.

#include <stdio.h>
#include <math.h>

int isRamanujan(int n)
{   
    
	int a,b,c,d,boolean,k;
	boolean=1;
	k=pow(n, 1/3);
	
    for (a=1;a<=k;a++)
    {
        k= pow((n-a*a*a), 1/3);
		for (b=1;b<=k;b++)
        {
        	k= pow((n-a*a*a-b*b*b), 1/3);
            for (c=1;c<=k;c++)
            {
            	k= pow((n-a*a*a-b*b*b-c*c*c), 1/3);
                for (d=1;d<=k;d++)
                {
                    if (((a*a*a+b*b*b)==(c*c*c+d*d*d)) && n==(a*a*a+b*b*b) && a!=b && b!=c && c!=d && b!=d && a!=d && a!=c) boolean=0;
                    
                }
            }
        }
    }
    
    return boolean;
    
}

int main()
{
    int n,i;
    scanf("%d", &n);
    
    for (i=1;i<=n;i++)
    {
        if (isRamanujan(i)==0) printf("%d ",i);
    }
    
    return 0;
    
}

sao giờ mình sửa theo bác mà không in ra gì :(.
cái trước của mình có in ra chỉ là hơi lâu thôi.

1 chia 3 bằng 0 mà bạn

hjxx thế phải làm sao để căn bậc 3 hả bác ?

Dùng tìm kiếm nhị phân thì có thể tìm căn bậc r của n:

def introot(n,r=2):
    lo,hi=0,n
    while lo!=hi-1:
        mid=(lo+hi)//2
        m=pow(mid,r)
        if m==n: return mid
        if m<n: lo=mid
        else: hi=mid
    return lo

câu 1 cho n tối đa là bao nhiêu, 10^5, 10^6 hay 10^9…

O(n) mà sợ gì 10^11 trở đi mới phê.

n < 10000 nghĩa là phải chạy x từ 1 tới 10000, chả lẽ mỗi lần xác định x có phải là số Ramanujan chỉ mất O(1) tức thì? Phải duyệt a từ 1 tới x^1/3 như vậy tối thiểu cũng phải ~ O(n^4/3) chứ?

m=pow(mid,r)

pow này là tượng trưng thôi.[quote=“tntxtnt, post:10, topic:55205, full:true”]
n < 10000 nghĩa là phải chạy x từ 1 tới 10000, chả lẽ mỗi lần xác định x là O(1) tức thì? Phải duyệt a từ 1 tới x1/3 như vậy tối thiểu cũng phải ~ O(n4/3) chứ?
[/quote]
Duyệt trên a, b, c suy ra d. O(n).

10000 bác ơi :(…

http://oeis.org/A001235

10000 thì copy mấy số trong list này rồi xuất những số < n thôi

vậy là 3 vòng lặp for lồng nhau à, chắc cách này hợp lý hơn