初項と数列の長さを全探索します。このとき、数列の要素の総積は、公差を大きくすると単調に増大するので、「公差がいくつまでなら総積が \(N\) 以下になるか？」は二分探索により求めることができます。

数列の長さが \(3\) 以上かつ公差が正であることから、初項は \(N^{1/3}\) 以下のみを考えれば十分です。また、初項も公差も正整数である長さ \(m\) の数列の総積は \(m!\) 以上になることから、数列の長さは \(O(\log N)\) までを考えれば十分です。

以上よりこの問題を \(O(N^{1/3}(\log N)^2)\) で解くことができました。

A[1] * ... * A[m] <= N は切り捨て整数除算 / を用いて N / A[1] / ... / A[m] > 0 と変形することでオーバーフローすることなく判定できます。

Writer解 (C++)

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
	ll N;
	cin >> N;
	
	auto calc=[&](int a, int n){
		int ok=0,ng=1e9;
		while(ng-ok>1){
			int mid=(ok+ng)/2;
			ll s=N;
			for(int i=0;i<n;i++)s/=a+i*mid;
			if(s)ok=mid;
			else ng=mid;
		}
		return ok;
	};
	
	ll ans=0;
	for(int a=1;a<=1e6;a++){
		int n=3;
		ll NN=N/a/(a+1)/(a+2);
		while(NN){
			ans+=calc(a,n);
			NN/=a+n;
			n++;
		}
	}
	cout << ans << endl;
}