HDU4473_Exam

很考验智商的一个题目，赛后看完别人的题解后秒懂了。

首先定义一个函数f(x)表示a,b的有序组合情况数使得a*b为x的一个约数。

现在给定你一个n，要你求出f(1)+f(2)+……+f(n)；

题目智商味道太浓厚，本屌表示智商拙计。

可以这样来考虑问题，a*b为x的一个约数，其实就等价于a*b*c=x，c为任意一个正整数。

所以整个问题转化为有多少个有序数对(a,b,c)使得a*b*c不大于n。

到这里问题就变得好办多了。

由于直接枚举复杂度过高，我们在枚举的时候可以假定a<=b<=c，同时把中间a，b，c是否相等的情况都记录下来。

这样在求解答案的时候只要排列一下就可以了。

所以我们在枚举a的时候，只要枚举的范围就是1到n^(1/3)，b需要枚举的范围就是n^(1/3)到n^(2/3)，这样算来整个题目的时间复杂度为n^(2/3)大约为2*10^7，可以承受的哦。

题目注意统计的时候，尽量避免不必要的运算。

 #include <cstdio>

 using namespace std;

 typedef long long ll;

 ll n,m,k,ans,i,j;

 int k1,k2,cas=;

 int main()

 {

     while (scanf("%I64d",&n)!=EOF)

     {

         ans=;

         for (i=; i*i*i<=n; i++) ;

         ans+=--i;

         for (; i; i--)

         {

             m=n/i;

             for (j=; j*j<=m; j++) ;

             ans+=*(m/i-i+--j-i);

             for (; j>i; j--) ans+=*(m/j-j);

         }

         printf("Case %d: %I64d\n",++cas,ans);

     }

     return ;

 }

巴特西

HDU4473_Exam

最新文章

热门文章