欧拉函数

洛谷P2158

欧拉函数

在数论，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目（因此φ(1)=1）。此函数以其首名研究者欧拉命名(Euler's totient function)，它又称为Euler's totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。 从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。

简单来说欧拉函数就是求从1到n-1中有多少个数与n互质。

欧拉函数的模板

 1 int a[maxn];
 2 void euler()
 3 {
 4     for(int i=1;i<=maxn;i++)
 5         a[i]=i;
 6         a[1]=0;
 7         for(int i=1;i<=maxn;i++)
 8         {
 9             if(a[i]==i)
10             {
11              for(int j=i;j<=maxn;j+=i)
12              a[j]=a[j]/i*(i-1);
13             }
14         }
15 }

应用

洛谷这道题，简单来说就是给一个N*N的矩阵，由左下角这个点可以和其他的点连多少条线，其中任意两条线不能交叉。我们很容易可以想到用斜率来处理，因为只要两条线的斜率不同他们就不会交叉，我们可以以左下角为原点建立坐标系，横纵坐标都为0到N-1,那么我们可以很容易得出如果一个点的坐标互质，那么它就满足题意，例如在4*4的矩阵中满足题意的有（1，0）（0，1）（1，1）（2，1）（1，2）（3，1）（1，3）（3，2）（2，3），并且因为对称关系，横纵坐标轴以及对称轴上的3个点我们做特殊处理，那么我们可以看到所有满足题意的点的横纵坐标都是互质的，那么我们只要根据对称 ，统计这样的数有多少个就可以了

 1 #include <iostream>
 2 #include <cstring>
 3 #include <string>
 4 #include <algorithm>
 5 #include <queue>
 6 #include <stack>
 7 #include <stdio.h>
 8 #include <cmath>
 9 #include <string.h>
10
11 using namespace std;
12 #define ll long long
13 #define maxn 40005
14 static const int WHITE=0;
15 static const int GRAY=1;
16 static const int BLACK=2;
17 static const int INF=(1<<20);
18 int a[maxn];
19 void euler()
20 {
21     for(int i=1;i<=maxn;i++)
22         a[i]=i;
23         a[1]=0;
24         for(int i=1;i<=maxn;i++)
25         {
26             if(a[i]==i)
27             {
28              for(int j=i;j<=maxn;j+=i)
29              a[j]=a[j]/i*(i-1);
30             }
31         }
32 }
33 int main()
34 {
35   freopen("C:\\Users\\16599\\Desktop\\in.txt","r",stdin);
36   int N,ans=0;
37   cin>>N;
38   euler();
39   for(int i=1;i<=N-1;i++)
40   {
41     ans+=a[i]*2;
42   }
43   if(N==1)
44   cout<<"0"<<endl;
45   else
46   cout<<ans+3<<endl;
47   return 0;
48 }