牛客训练赛25-A-因数个数

题目链接https://www.nowcoder.com/acm/contest/158/A

无语。。。这题很迷啊，原谅我的菜，刚开始想用预处理欧拉筛和前缀和，可是这题太血崩了，这样一样要遍历，1-e9的范围，后来翻网上题解，发现其实是个还算经典的问题

这题可以用离散和做嘛，如何离散和？？？先别着急，我们先想想，为啥这题不用欧拉函数做。。。

我们平时欧拉函数的题，都还能算比较难的题了，这题不仅仅加大了范围，还要求1-n的因数个数，我们只有另寻其它方法

我们不如写出1-10的因数组成（比赛一定要动笔啊）想是没有用的。。。干想没有任何结果。。。

1----1

2----1 2

3----1 3

4----1 2 4

5----1 5

6----1 3 6

7----1 7

8----1 2 4 8

9----1 3 9

10---1 2 5 10

我们可以找一下规律，发现一个还算奇特的现象，1-n的因数个数和可以写成n/1+n/2+n/3+n/4-----n/n，如何解释？？？其实很简单，可以把这个式子看成1-n范围

内的因数为 i 在1-n范围内的个数，但是求这个式子，仍然是o（n）的操作，我们仅仅支持o(logn)的操作，我们发现，这是式子是个离散和，并转化为面积，但是这个面积对称，因此我们只需要算到一个sqrt（n）就行，并把求的面积加二，但是面积是算重一部分（画出来你就知道了）我们只需要减去就行

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#define ll long long
using namespace std;
int main(){
  int t,x;
  scanf("%d",&t);
  while(t--){
    ll n,m;
    scanf("%lld",&n);
    ll ans=0;
    int mid=sqrt(n);
    for(int i=1;i<=mid;i++){
        ans+=n/i;
    }
     ans=ans*2;
    ans=ans-mid*mid;
    printf("%lld\n",ans);
  }
  return 0;
}