找新朋友 HDU

题意：

求出来区间[1,n]内与n互质的数的数量

题解：

典型的欧拉函数应用，具体见这里：Relatives POJ - 2407 欧拉函数

代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<math.h>
 6 using namespace std;
 7 typedef long long ll;
 8 const int maxn=100005;
 9 int oula(int n)
10 {
11     int ans=n;
12     for(int i=2; i<=sqrt(n); ++i)
13     {
14         if(n%i==0)
15         {
16             ans=ans-ans/i;
17             n/=i;
18             while(n%i==0)
19                 n/=i;
20         }
21     }
22     if(n>1)
23         ans=ans-ans/n;
24     return ans;
25 }
26 int main()
27 {
28     int t;
29     scanf("%d",&t);
30     while(t--)
31     {
32         int n;
33         scanf("%d",&n);
34         int result=oula(n);
35         printf("%d
",result);
36     }
37     return 0;
38 }