题目链接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;
}