首页 > ACM题库 > HDU-杭电 > HDU 4473-Exam-数论-[解题报告]HOJ
2015
07-16

HDU 4473-Exam-数论-[解题报告]HOJ

Exam

问题描述 :

Rikka is a high school girl suffering seriously from Chūnibyō (the age of fourteen would either act like a know-it-all adult, or thinks they have special powers no one else has. You might google it for detailed explanation) who, unfortunately, performs badly at math courses. After scoring so poorly on her maths test, she is faced with the situation that her club would be disband if her scores keeps low.
Believe it or not, in the next exam she faces a hard problem described as follows.
Let’s denote f(x) number of ordered pairs satisfying (a * b)|x (that is, x mod (a * b) = 0) where a and b are positive integers. Given a positive integer n, Rikka is required to solve for f(1) + f(2) + . . . + f(n).
According to story development we know that Rikka scores slightly higher than average, meaning she must have solved this problem. So, how does she manage to do so?

输入:

There are several test cases.
For each test case, there is a single line containing only one integer n (1 ≤ n ≤ 1011).
Input is terminated by EOF.

输出:

There are several test cases.
For each test case, there is a single line containing only one integer n (1 ≤ n ≤ 1011).
Input is terminated by EOF.

样例输入:

1
3
6
10
15
21
28

样例输出:

Case 1: 1
Case 2: 7
Case 3: 25
Case 4: 53
Case 5: 95
Case 6: 161
Case 7: 246

这是去年成都邀请赛的题,听zz_1215说这个数论题很独特,果然如此,现场赛只有3个队通过竟然。。。后来看了题解,顿时惊呆。。

首先先来看一个这样的题,问f(1)+f(2)+..+f(n),其中f(x)是x的约数的个数

这个问题可以转换为a*b<=n的解的个数来解决。(PS:这个问题以前见过,但我没有往这方面想,我对这道题的理解是枚举约数,然后分别计算,答案是n/1+n/2+..+n/n

然而不同的理解方式显然有着很大的区别,如果按照第一种思维方式去理解,显然拿到这道题后就得心应手了

言归正传,这道题是不是可以转化为a*b*c<=n的解的个数。。。?OK,附代码吧。

#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    __int64 i,j,n,zs;
    int cas=0;
    while (scanf("%I64d",&n)!=EOF)
    {
          cas++;
          zs=0;
          for (i=1;i*i*i<=n;i++)
              for (j=i;i*j*j<=n;j++)
              {
                  __int64 k1,k2;
                  k1=j;
                  k2=n/(i*j);
                  if (i!=j)  
                  {
                             zs=zs+6*(k2-k1+1);
                             zs-=3;
                  }
                  else 
                  {
                       zs=zs+3*(k2-k1+1);
                       zs-=2;
                  }
              }
          printf("Case %d: %I64d\n",cas,zs);
    }
    return 0;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/liverpippta/article/details/9225759