问题标题: 酷町堂：1590 互质数

gcd是求两数的最大公因数，gcd(i,n)=1的意思就是i和n的最大公因数为1，即这两个数互质（互质的意思就是两个数的最大公因数为1，例如1和任何数的最大公因数都为1，所以1和所有数都互质，相邻的两数一定互质，如5和6，7和8，质数和不是此数倍数的非0自然数一定互质，如7和41,5和39）。

这一题可以用辗转相除法求两数的最大公因数，代码如下：

int r=m%n;
    while(r)
    {
        m=n;
        n=r;
        r=m%n;
    }

对于这一题，在外面加一个循环即可。

for(int i=1;i<=n;i++)
    {
        int i1=i;
        int r=n%i1;
        int n1=n;
        while(r)
        {
            n1=i1;
            i1=r;
            r=n1%i1;
        }
        if(i1==1)
            count++;    
    }

最后输出count。

但这一题属于高级数据结构，单纯用这种方法自然是不行的，具体怎么做我也不清楚。这种方法可以得到20分，供你参考用。

http://wenda.codingtang.com/questions/2159/

http://wenda.codingtang.com/questions/2183/

http://wenda.codingtang.com/questions/2188/

求解

1

用数论不超时

代码如下：（有注释）

    定义 N,n;  
    while(scanf("%d",&N)!=EOF)  
    {  
        如果(N==0)  
            break;  
         n=N;  
         循环(int i=2;i<=sqrt(N);i++)//使用欧拉函数解决的问题；  
              如果(N%i==0)  
              {  
                  n=n/i*(i-1);         
                 while(N%i==0)  
                   N/=i;          //根据欧拉函数的的定义；  
             }  
       如果(N>1)  
          n=n/N*(N-1);      //这一步不能遗忘；  
                     printf("%d\n",n);  
    }