HDU 4473 Exam 枚举

原题转化为求a*b*c <=n中选出两个数组成有序对<a,b>的选法数。

令a<=b<=c....

分情况讨论：

（1）全部相等，即a = b = c.

选法有n^(1/3).

（2）有两个相等，则设相等的值为i,枚举i = 1到i*i <= n ，剩下的一个数的最大值为t = n/(i*i).当t >=i时，t = i这一种要删除，因为t = i则三个数都相等了，这种选法有3种，所以ans += 3*(t-1).t<i就ans += 3*t;

（3）三个数都不相等，则枚举a,b,其中b>a,剩下的数的最大值s = n/(a*b),如果s <= b,不满足····，假设s>b，则ans += 6*(s - b ).

分类讨论时要不重复，不遗漏······

贴代码：

 #include<cstdio>

 typedef long long int LL;

 int main()

 {

 //        freopen("in.txt","r",stdin);

     LL n,ans;

     int kase = ;

     while(~scanf("%I64d",&n))

     {

         ans = ;

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

         int A = ans;

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

         {

             LL t = n/(i*i);

             if(t >= i) ans += *(t-);

             else ans += *t;

         }

         for(LL a=; a<=A; ++a)

         {

             LL k = n/a;

             for(LL b=a+; b*b <= k; ++b)

             {

                 LL s = n/(a*b);

                 if(s > b) ans += *(s-b);

             }

         }

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

     }

     return ;

 }

注意n为long long int ·······

巴特西

HDU 4473 Exam 枚举

最新文章

热门文章