[暴力]HDU 4473——Exam

xiaoxiao2021-02-28  42

题目梗概

求正整数a,b,c,a*b*c<=n的方案数。

解题思路

从小到大枚举每个数,控制每个数范围就可以了。 考虑以下代码:

#include<cstdio> #include<cmath> #define LL long long 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) 不会过。

转载请注明原文地址: https://www.6miu.com/read-1000029.html

最新回复(0)