جواب خودم:

ایده‌ی نخست:

می‌توان ثابت کرد، به ازای هر $a,b,c ,(a,b)=1,(a,c)=1,(b,c)=1,a^2+b^2=c^2 $ دقیقا یک $n,m$ وجود دارند به طوری که: (فرمول ۳.۱) $$ a=m^2-n^2,b=2nm,c=m^2+n^2 $$ همچنین اگر $a,b,c$ نسبت به هم اول نباشند، به طور مثال $(a,b)=k→(a,c)=(b,c)=k :$ $$ a^2+b^2=c^2=(a' k)^2+(b' k)^2=(c' k)^2↔a'^2+b'^2=c'^2
$$ که $k$ عددی بین $۱$ تا $⌊n/c⌋$ هست پس اگر یک $a,b,c$ که $ a < b < c$ و $a,b$ نسبت به هم اول بودند و شرایط مسئله را داشتند پیدا کردیم کل هزینه برای این a,b,c و مضاربشان برابر با (فرمول ۳.۲) $$ ((1+⌊n/c⌋)×⌊n/c⌋)/2×(a+2b+3c) $$ می‌شود، برای پیدا کردن $a,b,c$ ها از فرمولی که در ابتدا گفتم استفاده می‌کنیم و با توجه به اینکه $n,m≤√N$ می‌توانیم روی همه‌ی n,m ها فور بزنیم، اگر $a,b,c$ با شرایط مسئله را ساخت مقدار جواب را به اضافه‌ی فرمول ۳.۲ کنیم. خوب دیگه، میشه $O(n)$

کد:

http://paste.white-crow.ir/view/309/2y10swvGxB2VIos

ایده‌ی دوم

با تشکر از آرش محمودیان و حمیدرضا هدایتی که این راه‌حل را به من گفتند، این راه حل نسبت به راه حل اول به ذهن نزدیک‌تره و ممکنه سر امتحان به ذهن فرد بیاد! (من انتظار نداشتم ایده‌ی نخست به ذهن کسی بیاد سر مسابقه :) ) $$ a^2+b^2=c^2→a^2=c^2-b^2=(b-c)(b+c)=a^2 $$

خوب، می‌دونیم $a$ عددی بین یک تا $n$ است، $(b-c)$ هم حتما مقسوم علیه‌ای از $a^2$ است، پس روی همه‌ی مقسوم علیه های $a^2$ فور میزنیم و چک می‌کنیم شرایط مطلوب مسئله رو داره یا نه ، با بهینه‌سازی این راه حل احتمالا می‌توان $O(n^{4/3})$ پیاده سازیش کرد.