XTU,C语言,GCD
2021/11/29 23:09:28
本文主要是介绍XTU,C语言,GCD,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
a和b的最大公约数(Greatest Common Divisor)是最大的d,d能整除a和b。
如果gcd(a,b)=1,我们就称a和b是互素的。
给一个区间[a,b],求与6互素的数的个数。
比如区间[1,10],与6互素的数为1,5,7,所以一共是3个。
输入
第一行是一个整数K(K≤10,000),表示样例的个数。
每个样例占一行,为区间[a,b],(1≤a≤b≤1,000,000,000)
输出
每行输出一个样例的结果
样例输入
2 1 10 1 1000000000
样例输出
3 333333333
6的因数有1、2、3与6,如果一个数与6互素,则这个数的因数中一定没有2与3.
所以我们只需要求a到b之间既不是2的倍数又不是3的倍数的数的数量即可。
#include<stdio.h> int s(int b); int main() { int k,a,b; scanf("%d",&k); while(k--) { scanf("%d%d",&a,&b); printf("%d\n",s(b)-s(a-1)); } } int s(int b)//用来求从1到b中与6互素的数的个数 { int sum,er,san,liu; er = b / 2; san = b / 3; //有些数既是2的倍数又是3的倍数,存在减去2次的情况 liu = b / 6; //因为6的倍数既是2的倍数又是3的倍数 sum = b-er-san+liu;//所以加上6的倍数就能弥补多减去的个数 return sum; }
这篇关于XTU,C语言,GCD的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升