题解 P8443 【gcd.】

· · 个人记录

蛮简单的一道题，确实符合普及组T1送分的特点。
一个很简单的结论：相邻两个数的最大公约数一定为1
所以这题我们就可以分类讨论，如果\lfloor \frac{l}{x}\rfloor和\lfloor \frac{r}{x}\rfloor的值相等，那么很容易知道\lfloor \frac{l}{x}\rfloor~\lfloor \frac{r}{x}\rfloor的最大公约数就是他们本身。否则一定会出现相邻的数，gcd只可能为1。
于是这题就这么愉快的水过去了

#include<bits/stdc++.h>
using namespace std;

#define int long long

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int t;

signed main()
{
    t = read();
    while(t --)
    {
        int l = read(), r = read(), x = read();
        if(l / x == r / x) cout << l / x << endl;
                      else cout << 1 << endl; 
    }
    return 0;
}