C - ABC conjecture Editorial by physics0523
(ユーザー解説の気持ちで書いています)
\(C\) についての境界条件を正確に詰めたくない場合は、以下のように実装するという手もあります。
\(A,B\) 全探索は本解説と同じですが、 \(C\) の上限を探索する際に \(\max (B,\lfloor \frac{N}{A*B} \rfloor -5) \) から始める(おおよその上限のアタリを付けて細かなところを実際に探索していく方針です)ことで一番内側のループの実行時間を定数時間とすることができます。
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n,cnt=0;
cin >> n;
for(long long a=1;a*a*a<=n;a++){
for(long long b=a;a*b*b<=n;b++){
long long uc;
for(long long c=max(b,(n/(a*b))-5);;c++){
if(a*b*c<=n){uc=c;}else{break;}
}
//cerr << a << ' ' << b << ' ' << uc << '\n';
cnt+=(uc-b+1);
}
}
cout << cnt << '\n';
return 0;
}
posted:
last update: