费马定理&欧拉定理

费马定理:

a^p≡a(mod p)

其中p为质数，且a不是p的倍数

证明：

。。。。。

欧拉定理：

a^φ（p）≡1(mod p)

φ（x）（欧拉函数）为小于等于x且与x互质的数的个数

φ（x）=∏（pi-1）*p_i^ki-1其中pi表示 x的质因数，ki表示这种质因数的个数

特别的对于质数 φ（x）=x-1。

欧拉函数的代码实现：

 #include<cstdio>

 #include<Iostream>

 using namespace std;

 int ol(int x)

 {

       int ans=;

       for(int i=;i*i<=x;++i)

       {

           if(x%i==)

          {

              x/=i;

              ans*=i-;

          }

          while(x%i==)

         {

             x/=i;

              ans*=i;

          }

      }

      if(x>) ans*=x-;

      return ans;

  }

  int main()

  {

      int a;

      scanf("%d",&a);

     printf("%d",ol(a));

      return ;

  }

最后函数里那个如果x>1,ans*=x-1一开始让我很懵，后来一想，如果这个数将所有的质因数除过一遍之后，剩下的数如果不是1，那么剩下的肯定只有一个并且是个质数(证明很显然)

巴特西

费马定理&欧拉定理

最新文章

热门文章