P8443 gcd. 题解

miaohongxuan · 2022-07-28 08:48:06 · 个人记录

作为一个初中生，鄙人的解题方法不是非常高明，如有错误之处，请各位大佬指出。

我是从样例入手进行分析的。

• 对于第一组数据， x=1 ， \lfloor \frac{l}{x}\rfloor=l,\lfloor \frac{l+1}{x}\rfloor=l+2,\cdots,\lfloor \frac{r}{x}\rfloor=r 为相邻的正整数，最大公因数必为 1 。
• 对于第二组数据， \lfloor \frac{l}{x}\rfloor=\lfloor \frac{l+1}{x}\rfloor=\cdots=\lfloor \frac{r}{x}\rfloor ，又因为 \lfloor \frac{l}{x}\rfloor<\lfloor \frac{l+1}{x}\rfloor<\cdots<\lfloor \frac{r}{x}\rfloor ，所以只要知道 \lfloor \frac{l}{x}\rfloor=\lfloor \frac{r}{x}\rfloor ，即可确定数据属于这一种情况。多个相等的正整数求最大公因数，一定是那个正整数，也就是 \lfloor \frac{r}{x}\rfloor 。
• 对于第三组数据， l=r ，因为题目定义一个正整数的最大公约数是它自身，所以答案是 \lfloor \frac{r}{x}\rfloor 。
• 对于其他的情况来说，几个相邻的正整数除以一个相同的正整数，结果也必为相邻的正整数，所以最大公因数必为 1 。

在对这些情况进行整理，我们发现：

• 当 \lfloor \frac{l}{x}\rfloor=\lfloor \frac{r}{x}\rfloor 时，输出 \lfloor \frac{r}{x}\rfloor 。
• 其他情况下，均输出 1 。

代码：

#include <bits/stdc++.h>
using namespace std;
long long l,r,x,T;//不开longlong见祖宗
int main(){
    cin >> T;
    while(T--){
        if(l/x == r/x){
            cout << l/x << endl;
            continue;
        }
        cout << 1 << endl;
    }
    return 0;
}

虽然做完题之后可以通过事后诸葛亮的方式做出更简单的分析，但是鄙人希望鄙人的最朴素的做题经历对你有帮助，谢谢。