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));//根号nfor(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;
}