费马定理&欧拉定理
费马定理:
ap≡a(mod p)
其中p为质数，且a不是p的倍数
证明：
。。。。。
欧拉定理：
aφ（p）≡1(mod p)
φ（x）（欧拉函数）为小于等于x且与x互质的数的个数
φ（x）=∏（pi-1）*piki-1 其中pi表示 x的质因数，ki表示这种质因数的个数
特别的对于质数 φ（x）=x-1。
欧拉函数的代码实现：
1 #include<cstdio> 2 #include<Iostream> 3 using namespace std; 4 int ol(int x) 5 { 6 int ans=1; 7 for(int i=2;i*i<=x;++i) 8 { 9 if(x%i==0) 10 { 11 x/=i; 12 ans*=i-1; 13 } 14 while(x%i==0) 15 { 16 x/=i; 17 ans*=i; 18 } 19 } 20 if(x>1) ans*=x-1; 21 return ans; 22 } 23 int main() 24 { 25 int a; 26 scanf("%d",&a); 27 printf("%d",ol(a)); 28 return 0; 29 }
最后函数里那个如果x>1,ans*=x-1一开始让我很懵，后来一想，如果这个数将所有的质因数除过一遍之后，剩下的数如果不是1，那么剩下的肯定只有一个并且是个质数(证明很显然)
投递阿里巴巴等公司10个岗位 >
