Zeldain Garden

题意：

问[L,R]内所有数的因子的数量和

题解：

如果传统暴力做肯定不行
我们来找找规律：

数字： 因子数目 1~n的因子数和
1		1			1
2		2			3=2+1/
3		2			5=3+1+1
4		3			8=4+2+1+1
5		2			10=5+2+1+1+1
6		4			14=
7		2			16=
8		4			20=
9       3           23=9+4+3+2+1+1+1+1+1

有发现什么规律？
可以推出：1—n的因子数和 =∑ (int)n/i （i是从1到n）
问我咋推出来的？
额。。“直觉”算能力吗？我在纸上把因子数和进行拆分就发现这样的规律
但是注意题目中的数据是1e12，感觉直接做还是不准，，O(n)肯定不行，此时就要往O(log n)或者O(√n)的方向去想
∑ (int)n/i其实是函数y=n/x的一个离散和
而这个函数是关于y=x对称，对称点为（√n，√n），图像面积是对称的，所以我们只需要求出√n数据范围内的答案即可，然后乘以2减去√n√n，其实就是去掉重复的正方形面积，正方形边长是√n，这样一来复杂度不就降低了，1e12就没问题了
答案就是 ans2 - t *t
t=sqrt(n)
小于sqrtN的因子在所有数中有多少：∑N/i (i=1,…,sqrtN)
大于sqrtN的因子在所有数中有多少: ∑N/i (i=1,…,sqrtN)
但是两者有重复部分
“因子对”里的数都小于sqrtN的那些因子其实被重复加了一遍，多加了Q * Q个因子

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;//用long long
ll work(ll n)//计算一个数的因子之和
{
   
    ll ans=0;
    ll t=sqrt(double(n));//根号n
    for(int i=1;i<=t;i++){
   
        ans=ans+n/i;
    }
    ans=ans*2-t*t;//公式求和
}
int main ()
{
   
    ios::sync_with_stdio(false);
    ll n,m;
    cin>>n>>m;
    cout<<work(m)-work(n-1)<<endl;//从n-m的，跟前缀和差不多原理
    return 0;
}