CSP/信奥赛C++刷题训练：经典信奥数学例题（4）：洛谷P8443 ：gcd.

CSP/信奥赛C++刷题训练：经典信奥数学例题（4）：洛谷P8443 ：gcd.

题目背景

与你借星火，容我题山河。

题目描述

$T$ 组数据，每一组数据给定 $l,r,x$，试求：$\gcd (\lfloor \frac{l}{x}\rfloor ,\lfloor \frac{l+1}{x}\rfloor ,\cdots ,\lfloor \frac{r}{x}\rfloor )$ 的值。

• 其中 $\gcd$ 表示求最大公约数，例如 $\gcd (6,9)=3$，$\gcd (2,4,8)=2$，$\gcd (5,6,7)=1$。特别地，我们定义一个正整数的最大公约数是它自身。
• $\lfloor x\rfloor$ 表示 $x$ 向下取整，例如 $\lfloor 3.14\rfloor =3$。

输入格式

第一行输入一个正整数 $T$，表示数据组数。

对于每一组数据，输入一行三个正整数 $l,r,x$，以空格隔开。

输出格式

对于每一组数据，输出一行，一个正整数表示答案。

样例 #1

样例输入 #1

4
3 6 1
8 11 4
4 4 3
7 16 2

样例输出 #1

1
2
1
1

提示

【样例解释和说明】

样例中的 $T=4$，说明有 $4$ 组数据。

• 对于第一组数据，$l=3,r=6,x=1$，即求 $\gcd (\lfloor \frac{3}{1}\rfloor ,\lfloor \frac{4}{1}\rfloor ,\lfloor \frac{5}{1}\rfloor ,\lfloor \frac{6}{1}\rfloor )=1$。
• 对于第二组数据，$l=8,r=11,x=4$，即求 $\gcd (\lfloor \frac{8}{4}\rfloor ,\lfloor \frac{9}{4}\rfloor ,\lfloor \frac{10}{4}\rfloor ,\lfloor \frac{11}{4}\rfloor )=\gcd (2,2,2,2)=2$。
• 对于第三组数据，$l=4,r=4,x=3$，即求 $\gcd (\lfloor \frac{4}{3}\rfloor )=1$。
• 对于第四组数据，类似可得结果是 $1$。

【数据范围】

• 对于 $10\%$ 的数据，$x=1$。
• 另有 $10\%$ 的数据，$l=r$。
• 另有 $20\%$ 的数据，$r-l\le 10^5$。
• 对于上述的前 $40\%$ 的数据，$1\le x\le l\le r\le 10^9$。
• 对于所有数据，$1\le x\le l\le r\le 10^{18}$，$1\le T\le 10$。

AC代码

#include<bits/stdc++.h>
using namespace std;
//思路：显然，l/x , (l+1)/x,...,r/x是连续的整数，而且，显然有gcd(c,c+1)=1
//所以，只要l/x != r/x,结果就为1
//如果两者相等，答案就是l/x 
long long t,l,r,x;
int main(){
cin>>t;
while(t--){
cin>>l>>r>>x;
if(l/x != r/x) cout<<1<<endl;
else cout<<l/x<<endl;
}
return 0;
}

文末彩蛋：

点击王老师青少年编程主页有更多精彩内容

原文地址：https://blog.csdn.net/weixin_66461496/article/details/143616288

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！