费马定理&欧拉定理

费马定理:

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。

欧拉函数的代码实现：

 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-23 15:29

华为10.23一面

介绍了智驾项目经历，面试官一直在问我短视频推荐算法，甚至问我BEV怎么用到短视频推荐算法里，？？？？？？认真的吗？手撕代码是力扣410，hard，直接裂开，光速秒挂

点赞评论收藏

10-23 15:03

早稲田大学 C++

网易雷火游戏研发工程师面经

timeline：  07-15 投递 08-09 笔试 08-19 一面 08-20 二面 09-19 三面 09-22 测评 09-25 hr面 10-23 oc  一面 40m  自我介绍 1-9 的数字，随机抽取三个不重复的数，和是奇数的组合有多少种 移动构造可以是 T(const T&&); 吗 左值可以绑定到右值引用吗 右值引用可以绑定到 const 左值引用吗 一个绳子分成三部分，求组成三角形的概率 给一个中缀表达式，求后缀表达式 点到直线的距离公式 源文件到可执行文件的过程 C++ 多态 堆和栈的区别 map 和 unordered_map 的区别 冒泡排序是稳...

梦雨雨：同学，瞅瞅我司，医疗独角兽～我的主页最新动态，绿灯直达，免笔试～

点赞评论收藏

09-13 22:55

湖北大学单片机

双非本all in工作，目前一个面试都没有，心乱如麻

知道自己家境不好all in工作，没敢想考研，投了几十家都是已投递。改了简历投嵌入式和硬件一点波浪都没有。

亲爱滴达瓦里氏：又有嵌软又有FPGA又有硬件的，三个方向显得你的简历太杂糅了，展示不出你在某一个方向有哪些技术栈。基本上也不会有企业会去招一个本科的全栈工程师。HR一般是看你的技术栈是否和招聘要求匹配才发面试的。如果你想三个方向都试试的话还是建议你分成三份不同的简历根据不同岗位来投。多看看****或牛客上面的招聘信息，根据上面要求的技术栈来写简历。看了你的帖子经历这一块还是过关的，不过看的每个方向都会一点，但每个方向优势都不突出。还有就是要海投，你这才几十份算不了啥。去年投了一两百份的大有人在。多去跑跑线下招聘吧，有机会继续搞份实习，后面转正机会大些。有条件就多往北上广深投吧。武汉竞争还是太激烈了。

我的秋招日记

点赞评论收藏