数学专题

发现自己数学太菜了，所以练练！(

CF1780E Josuke and Complete Graph

链接：https://codeforces.com/contest/1780/problem/E

考虑$gcd$本质上是个啥。

假设我们现在知道某个数$d$，那么两个数$a$和$b$的$gcd$是$d$的条件其实是：

$a = k_1 d$,$b =k_2 d$且$(k_1,k_2) = 1$

又因为$(x,x+1) = 1$，所以其实$k_1$和$k_2$最接近的时候是差$1$

那么，我们现在假设我们枚举出某个数$d$，考虑什么时候$d$才能作为最大公约数出现在$[L,R]$之间

设第一个出现在$[L,R]$之间的$d$的倍数是$k_1 d$，则只要$(k_1 + 1) d$也在$[L,R]$内，$d$就能作为答案。

$k_1 = [\frac{L}{d}]$,$[ ]$表示上取整

有$(k_1 + 1) d <= R$

$d<=\frac{R}{k_1 + 1}$

显然，$k_1$是可以整除分块的。分块的过程中，$ [\frac{L}{d}] = k_1$时,范围为$[l,r]$

把两个$d$的范围取个交集，就是我们可以成为答案的$d$

在上整除分块中，$1$要单独处理一下。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int T;
    cin>>T;
    while (T--){
        long long L,R;
        cin>>L>>R;
        long long ans = 0;
        ans = max(0ll,R/2-L+1);
        for (long long l=1,r;l<=L;l=r+1){
            long long t = ceil(double(L)/double(l));
            if (t == 1) break; 
            r = (L-1)/(t-1);
            ans += max(0ll,min(r,R/(t+1)) - l + 1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}