2021年ICPC国际大学生程序设计竞赛-C

原题链接：https://ac.nowcoder.com/acm/contest/35232/C

题意

在区间 $[l,r]$ 内任意选取 $k$ 个数求最大公因数，问有多少种可能的结果。

• $1\leq l\leq r\leq 10^{12},$
• $2\leq k\leq r-l+1$

题解

数学本质

首先，显然有：

• $(b-a)$ 是 $gcd(a,b)$ 的倍数。

由此可得：

• $gcd(a,a+1)=1.$

于是有：

• $gcd(ax,(a+1)x)=x.$

所以最紧凑的 $k$ 个以 $x$ 为最大公因数的数必然是：

• $ax,(a+1)x,…,(a+k-1)x.$

所以 $[l,r]$ 中能选出 $k$ 个以 $x$ 为最大公因数的数等价于：

• 设 $t$ 是不小于 $l$ 的最小的 $x$ 的倍数，则 $t+(k-1)x\leq r.$

整理一下可以得到，题意是求满足

$$kx+\lfloor\frac{l-1}{x}\rfloor x\leq r$$

的 $x$ 的个数。

计数方法

看了很多人ac的代码是用二分来做的，即认为 $x$ 成立则 $x-1$ 一定成立。这显然是错误的，对于数据

12 24 3

来说，$6$ 成立但是 $5$ 不成立，用二分的代码跑出来的答案都是 $6$ 种，实际上答案只有 $5$ 种。

上式的关键是 $\lfloor\frac{l-1}{x}\rfloor$ 的计算。

当 $x\geq l$ 时，$\lfloor\frac{l-1}{x}\rfloor=0$，这部分的答案是 $max{\frac{r}{k}-l+1,0}.$

当 $x<l$ 时，可以对 $\lfloor\frac{l-1}{x}\rfloor$ 的取值分段讨论：

• $x\in (\frac{l-1}{2},l-1],\lfloor\frac{l-1}{x}\rfloor=1;$
• $x\in (\frac{l-1}{3},\frac{l-1}{2}],\lfloor\frac{l-1}{x}\rfloor=2;$
• $x\in (\frac{l-1}{4},\frac{l-1}{3}],\lfloor\frac{l-1}{x}\rfloor=3;$
• …

正解是对上面每一段单独解不等式并把答案累加。

这样做的正确性是显然的，问题在于 $l$ 的值很大时，这样分段是否会超时。实际上，这样分段的时间复杂度是 $O(\sqrt{l})$，对于本题来说是不会超时的。

代码

#include<iostream>
#include<algorithm>

int main(){
    long long l,r,k;
    std::cin>>l>>r>>k;

    long long ans = std::max(r/k-l+1,0ll);
    l--;
    for(long long i = 1;i <= l;){
        long long t = l/(l/i);
        ans+=std::max(std::min(r/(k+l/t),t)-i+1,0ll);
        i = t + 1;
    }
    std::cout<<ans<<std::endl;
}