1541: 蓝桥杯算法提高VIP-欧拉函数（时间复杂度n*logn）

解题思路:

对于两个数互质的定义是两数的公约数只有1，我们也可以理解为他们的最大公约数是1

一说到最大公约数就不得不提欧几里得法了

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。

计算公式gcd(a,b) = gcd(b,a mod b)。

它的时间复杂度是logn级别的

参考代码:

#include <stdio.h>
 
int gcd(int a,int b){
 if(a%b == 0)
  return b;
 gcd(b,a%b);
}

int main(){
 int i,n;
 int count = 0;
  
 scanf("%d", &n);
 for(i = 1; i <= n-1; i++){
  if(gcd(i,n) == 1)
   count++;
 }
 printf("%d", count);
  
 return 0;
}