[数据结构与算法]XTUC语言，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;
}