题目梗概
求正整数a,b,c,a*b*c<=n的方案数。
解题思路
从小到大枚举每个数,控制每个数范围就可以了。 考虑以下代码:
using namespace std;
const
int tt=
1000000007;
LL n,ans;
int tot;
int main(){
freopen(
"exam.in",
"r",stdin);
freopen(
"exam.out",
"w",stdout);
while(scanf(
"%lld",&n)==
1){
ans=
0;tot++;
for (LL i=
1;i
*i*i<=n;i++)
for (LL j=i;i
*j*j<=n;j++){
LL num=n/(i
*j)-j+
1;
if (i==j) ans+=
3*num-
2;
else ans+=
6*num-
3;
}
printf(
"Case %d: %lld\n",tot,ans);
}
return 0;
}
可以证明效率是
O(N23)
。 这题数据猥琐的啊,
O(n)
不会过。