首页 > 其他分享 >欧拉定理学习笔记

欧拉定理学习笔记

时间:2023-03-16 15:55:46浏览次数:46  
标签:phi int bm 定理 varphi pmod 笔记 欧拉 equiv

费马小定理:

当 $a,p \in \mathbb{Z} $ 且 \(p\) 为质数,$a \not\equiv 0 \pmod{p} $ 时,有:

\[a^{p-1} \equiv 1 \pmod{p} \]

故 \(a^b \equiv a^{b \mod (p-1)} \pmod{p}\)

欧拉定理:

当 $a,p \in \mathbb{Z} $ 且 \(\gcd(a,m)=1\) 时,有:

\[a^{\varphi(m)} \equiv 1 \pmod m \]

其中 \(\varphi(m)\) 为数论中的欧拉函数,即 \(1 \sim n\) 中与 \(n\) 互质的数的个数。

所以 \(a^{b} \equiv a^{b \mod \varphi(m)} \pmod m\).

扩展欧拉定理:

当 \(a,p \in \mathbb{Z}\) 时,有:

\[a^b\equiv \left\{\begin{matrix} a^b,b < \varphi(m)\\ a^{b \mod \varphi(m)+\varphi(m)}.b \geq \varphi(m) \end{matrix}\right. \pmod{m} \]

模板题code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a,m,phi=1;
int bm,flag;
int mul(int a,int b){int res=1;while(b) ((b&1)&&(res=1ll*res*a%m,0)),a=1ll*a*a%m,b>>=1;return res;}
int main()
{
	scanf("%d%d",&a,&m);a%=m;int tmp=m;
	for(int i=2;i*i<=tmp;i++)
	{
		if(tmp%i) continue;
		phi*=i-1;tmp/=i;
		while(tmp%i==0) phi*=i,tmp/=i;
	}
	if(tmp>1) phi*=tmp-1;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(bm=bm*10ll+(ch^'0'),(ch=getchar())>='0'&&ch<='9')
		if (bm>=phi) flag=1,bm%=phi;
	if(bm>=phi) flag=1,bm%=phi;
	if(flag) bm+=phi;
	printf("%d",mul(a,bm));
	return 0;
}

标签:phi,int,bm,定理,varphi,pmod,笔记,欧拉,equiv
From: https://www.cnblogs.com/ListenSnow/p/17222904.html

相关文章

  • 20212323严文霞--数据库读书笔记一(P3-P18,P31-P33)
    1.1数据库系统概述1.1.1数据库的4个基本概念数据(data)定义:描述事物的符号记录称为数据。数据有多种表现形式,例如数字、文字、图形、图像、音视频等;数据需要进行解......
  • 笔记本水冷改造记录
    1、前言最近用的电脑风扇总是起飞,打开idea都会像喷气飞机一样,使用时还经常卡顿。查看了一下闲鱼,当年8000多买的笔记本,3年半二手只能出大概3500。笔记本跟了一段时间了,还......
  • QT5笔记: 29. 文本文件读写
    例子:主要讲了QFile、QTextStream进行文本文件读写MainWindow.h#ifndefMAINWINDOW_H#defineMAINWINDOW_H#include<QMainWindow>QT_BEGIN_NAMESPACEnamesp......
  • QT5笔记: 30. 二进制文件读写
    Qt预定义类型文件*.stm标准二进制文件*.dat例子:MainWindow.h#ifndefMAINWINDOW_H#defineMAINWINDOW_H#include<QItemSelectionModel>#include<QMainWin......
  • QT5笔记:27. MDI应用程序设计
    MDI:MultipleDocumentInterface多窗口文档界面例子:MainWindow.h#ifndefMAINWINDOW_H#defineMAINWINDOW_H#include<QMainWindow>#include<QMdiSubWindow>......
  • 自主阅读笔记01《如何给详情页做性能优化的》
    笔记来源  公众号--架构师接口优化方案总结1.批处理批量思想:批量操作数据库,这个很好理解,我们在循环插入场景的接口中,可以在批处理执行完成后一次性插入或更新数据库,......
  • QT5笔记: 21. QStandardItemModel
    QStandardItemModel存放数据QItemSelectionModel选择项模型例子:本例子中QListView没有做任何处理,只是拖放至ui文件,设置了布局mainwindow.h#ifndefMAINWINDOW_H#......
  • QT5笔记: 22. 自定义代理
    代理作用:在界面发生编辑时可以指定编辑所用的组件,可以沟通Model和View自定义代理需要继承的基类和需要实现的方法使用步骤:继承QStyledItemDelegate,实现上面的四个......
  • 人月神话阅读笔记其一————“人月”神话
        首先在阅读之前就感觉很困惑,一部将编程的著作为什么会起一个这样的名字。再后来的阅读过程中也才逐渐明白,“人月”实际上就是一个具有欺骗性的神话。在编程中,“......
  • 《Hadoop Operations》读书笔记 - 2 - 第三章 MapReduce
    MapReduce,在这里实际上有两个含义,一个是一种分布式计算模型;另一个是某种特定实现,比如ApacheHadoopMapReduce。其设计目的是为了简化大规模、分布式、高容错性的数据处理应......