题目描述
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;
}