C互质个数

C互质个数

Time Limit:1000MS  Memory Limit:65536K

Total Submit:55 Accepted:27

Description

贝贝、妞妞和康康都长大了,如今,他们已届小学毕业,老师给贝贝出了一道强化计算的题目,让她做一大堆除法,以确定两个数之间是否有公共的因子,并且还要数清楚没有公因子的数对。可是,毕竟有些数太大了,量又太多了,即使她与妞妞和康康联手,也没有耐心在一个小时做完这种吃力的事情啊。虽然他们真的知道该怎么做,可是,他们的心早就飞到海边的沙滩上了,想尽情地玩,但眼看又不能。能不能帮他们“减负”,尽早放飞心情,那就要靠你了。

Input

输入若干组(≤100组)整数(每个整数n满足0< n < 2^32),每组整数(个数≤50)占一行(第一个数代表数字个数)。

**Output

**

对每组整数,输出其彼此互质的个数,每个结果单独占一行。

Sample Input

6 27 91 18 2 5 9
4 13 5 60 12

Sample Output

11
4
**Source**
#include 

int gcd(int i, int j)
{
    return j ? gcd(j, i % j) : i;
}

int main()
{
    int n, i, j;
    int a[50];
    while (~scanf("%d", &n))
    {
        for ( i=0; i




坚持原创技术分享,您的支持将鼓励我继续创作!
  • 本文作者: Fayne
  • 本文链接: 394.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!