SDAU暑假训练第二天----------数论(2)(2018/7/31)

2024-06-12 18:18

本文主要是介绍SDAU暑假训练第二天----------数论(2)(2018/7/31),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

今天上午还是看数论,下午有场练习赛,A了四个题,不是很难,个别题有点难想,比如逆向思维那个,另外读题能力很重要!!

目录

同余

同余式基本概念

同余的运算性质:

剩余类(只整理基础,复杂的剩余环涉及到了近世代数理论)

费马小定理

欧拉定理

1.欧拉函数的线性筛法(类比素数的线性筛法)

2.欧拉线性筛法求素数


同余

同余式基本概念

设m是大于1的正整数,a、b是整数,如果(a-b)|m,则称a与b关于模m同余,记作a≡b(mod m),读作a与b对模m同余。

显然,有以下事实

(1)若a≡0(mod m),则a|m;

(2)a≡b(mod m)等价于a与b分别用m去除,余数相同。

同余的运算性质:

1.反身性:a≡a (mod m);

2.对称性:若a≡b(mod m),则b≡a (mod m);

3.传递性:若a≡b(mod m),b≡c(mod m),则a≡c(mod m);

4.同余式相加/减:若a≡b(mod m),c≡d(mod m),则a+c≡b+d(mod m);a-c≡b-d(mod m);

5.同余式相乘:若a≡b(mod m),c≡d(mod m),则ac≡bd(mod m)。

6.线性运算:如果a ≡ b (mod m),c ≡ d (mod m),那么

(1)a ± c ≡ b ± d (mod m);

(2)a * c ≡ b * d (mod m)。

除法:若 https://gss2.bdstatic.com/-fo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D145/sign=cd84be1a25dda3cc0fe4bc2434e83905/48540923dd54564e14eac3bcb8de9c82d0584fa3.jpg ,则 https://gss3.bdstatic.com/7Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D160/sign=4cb6e858a064034f0bcdc6009fc27980/03087bf40ad162d9f59e44991adfa9ec8b13cdc6.jpg ,其中gcd(c,m)表示cm最大公约数

特殊地, https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D89/sign=ef053e40ebfe9925cf0c645935a8319b/5bafa40f4bfbfbed7e4810fa73f0f736afc31f25.jpg  https://gss0.bdstatic.com/-4o3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D90/sign=dfe0963ead1ea8d38e227804960a18fe/3812b31bb051f8196a0222cfd1b44aed2e73e714.jpg 

8.幂运算:如果 https://gss0.bdstatic.com/-4o3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D90/sign=14cdd9356e380cd7e21eaeeda044c115/71cf3bc79f3df8dc75b3a914c611728b461028ac.jpg ,那么 https://gss2.bdstatic.com/-fo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D106/sign=31c3e76bbf8f8c54e7d3c12f0c282dee/a686c9177f3e670957af647a30c79f3df9dc5583.jpg 

9. https://gss0.bdstatic.com/-4o3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D90/sign=14cdd9356e380cd7e21eaeeda044c115/71cf3bc79f3df8dc75b3a914c611728b461028ac.jpg n=m,则 https://gss0.bdstatic.com/-4o3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D86/sign=e40a66bb07f3d7ca08f63270f31fe992/e1fe9925bc315c6048804a6a86b1cb1349547719.jpg 

10. https://gss1.bdstatic.com/9vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D96/sign=bb16d9a4798b4710ca2ff1cac2ce631c/a8014c086e061d950bcc16bd70f40ad163d9caa8.jpg (i=1,2...n)  https://gss2.bdstatic.com/-fo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D182/sign=50ae88a3f6faaf5180e385b7be5594ed/c8177f3e6709c93dee7a2e72943df8dcd00054ae.jpg ,其中 https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D102/sign=b28572bcc23d70cf48faae0dcaddd1ba/c995d143ad4bd113be4b97b751afa40f4afb05b4.jpg 表示m1,m2,...mn最小公倍数


剩余类(只整理基础,复杂的剩余环涉及到了近世代数理论)

剩余类,设模为n,则根据余数可将所有的整数分为n类,把所有与整数a模n同余的整数构成的集合叫做模n的一个剩余类,记作[a]。并把a叫作剩余类[a]的一个代表元。

一个整数被正整数n除后,余数有n种情形:0,1,2,3,…,n-1,它们彼此对模n不同余。这表明,每个整数恰与这n个整数中某一个对模n同余。这样一来,按模n是否同余对整数集进行分类,可以将整数集分成n个两两不相交的子集。我们把(所有)对模n同余的整数构成的一个集合叫做模n的一个剩余类。每一个整数必包含在而且仅包含在上述一个集合里。②两个整数同在一个集合的充分必要条件是它们对模□同余。

剩余类的相关运算性质

交换律:([a]+[b])+[c]=[a]+([b]+[c])

交换律:[a]+[b]=[b]+[a]

分配率:[a]([b]+[c])=[a][b]+[a][c]

此外加减法:[a]+[0]=[0]+[a]=[a]     乘法:  [a][0]=[0][a]=[0]      [0]叫做零元      [a][1]=[1][a]=[a]      [1]叫做单位元


费马小定理

假如p是质数,且gcd(a,p)=1,那么 a^(p-1)≡1(mod p),例如:假如a是整数,p是质数,则a,p显然互质(即两者只有一个公约数1),那么我们可以得到费马小定理的一个特例,即当p为质数时候, a^(p-1)≡1(mod p)。

例题1:https://blog.csdn.net/zcy_2016/article/details/55054146

例题2:利用费马小定理计算

  除以13的余数


欧拉定理

欧拉定理,(也称费马-欧拉定理)是一个关于同余的性质。欧拉定理表明,若n,a为正整数,且n,a互质,则:

(对于正整数N,代表小于等于N的与N互质的数的个数,记作φ(N))

1.欧拉函数的线性筛法(类比素数的线性筛法)

线性时间内求出1~N的所有φ 有以下三条性质:

    ①:φ(p)=p-1

    ②:φ(p*i)=p*φ(i) (当p%i==0时)

    ③:φ(p*i)=(p-1)*φ(i) (当p%i!=0时)

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int prime[100001],mark[1000001];//prime是素数数组,mark为标记不是素数的数组
int tot,phi[100001];//phi为φ(),tot为1~i现求出的素数个数
void getphi(int N){phi[1]=1;//φ(1)=1for(int i=2;i<=N;i++){//从2枚举到Nif(!mark[i]){//如果是素数prime[++tot]=i;//那么进素数数组,指针加1phi[i]=i-1;//根据性质1所得}for(int j=1;j<=tot;j++){//从现求出素数枚举if(i*prime[j]>N) break;//如果超出了所求范围就没有意义了mark[i*prime[j]]=1;//标记i*prime[j]不是素数if(i%prime[j]==0){//应用性质2phi[i*prime[j]]=phi[i]*prime[j];break;}else phi[i*prime[j]]=phi[i]*phi[prime[j]];//应用性质3}}
}
int N;
int main(){cin>>N;getphi(N);for(int i=1;i<=N;i++){cout<<i<<":phi ( "<<phi[i]<<" )"<<endl;//输出phi(i)}
}

 

2.欧拉线性筛法求素数

求素数原来的经典埃拉特斯特尼筛法:时间复杂度为O(n loglog n)

void GetEven()
{int t=sqrt(N);for(int i=3; i<=t;i++){if(prime[i])for(int j=i*i; j <= N; j+=i)//筛掉i的倍数 prime[j]=false;}

欧拉线性筛法

const int MAXN=3000001;
int prime[MAXN];//保存素数 
bool vis[MAXN];//初始化 
int Prime(int n)
{int cnt=0;memset(vis,0,sizeof(vis));for(int i=2;i<n;i++){if(!vis[i])prime[cnt++]=i;for(int j=0;j<cnt&&i*prime[j]<n;j++){vis[i*prime[j]]=1;if(i%prime[j]==0)//关键 break;}}return cnt;//返回小于n的素数的个数 
}

 

这篇关于SDAU暑假训练第二天----------数论(2)(2018/7/31)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1054972

相关文章

数论入门整理(updating)

一、gcd lcm 基础中的基础,一般用来处理计算第一步什么的,分数化简之类。 LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } <pre name="code" class="cpp">LL lcm(LL a, LL b){LL c = gcd(a, b);return a / c * b;} 例题:

BUUCTF靶场[web][极客大挑战 2019]Http、[HCTF 2018]admin

目录   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 [web][HCTF 2018]admin 考点:弱密码字典爆破 四种方法:   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 访问环境 老规矩,我们先查看源代码

数论ZOJ 2562

题意:给定一个数N,求小于等于N的所有数当中,约数最多的一个数,如果存在多个这样的数,输出其中最大的一个。 分析:反素数定义:对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数。 性质一:一个反素数的质因子必然是从2开始连续的质数。 性质二:p=2^t1*3^t2*5^t3*7

POJ2247数论

p = 2^a*3^b*5^c*7^d 求形如上式的第n小的数。 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.u

MiniGPT-3D, 首个高效的3D点云大语言模型,仅需一张RTX3090显卡,训练一天时间,已开源

项目主页:https://tangyuan96.github.io/minigpt_3d_project_page/ 代码:https://github.com/TangYuan96/MiniGPT-3D 论文:https://arxiv.org/pdf/2405.01413 MiniGPT-3D在多个任务上取得了SoTA,被ACM MM2024接收,只拥有47.8M的可训练参数,在一张RTX

Spark MLlib模型训练—聚类算法 PIC(Power Iteration Clustering)

Spark MLlib模型训练—聚类算法 PIC(Power Iteration Clustering) Power Iteration Clustering (PIC) 是一种基于图的聚类算法,用于在大规模数据集上进行高效的社区检测。PIC 算法的核心思想是通过迭代图的幂运算来发现数据中的潜在簇。该算法适用于处理大规模图数据,特别是在社交网络分析、推荐系统和生物信息学等领域具有广泛应用。Spa

SigLIP——采用sigmoid损失的图文预训练方式

SigLIP——采用sigmoid损失的图文预训练方式 FesianXu 20240825 at Wechat Search Team 前言 CLIP中的infoNCE损失是一种对比性损失,在SigLIP这个工作中,作者提出采用非对比性的sigmoid损失,能够更高效地进行图文预训练,本文进行介绍。如有谬误请见谅并联系指出,本文遵守CC 4.0 BY-SA版权协议,转载请联系作者并注

Java基础回顾系列-第二天-面向对象编程

面向对象编程 Java类核心开发结构面向对象封装继承多态 抽象类abstract接口interface抽象类与接口的区别深入分析类与对象内存分析 继承extends重写(Override)与重载(Overload)重写(Override)重载(Overload)重写与重载之间的区别总结 this关键字static关键字static变量static方法static代码块 代码块String类特

Detectorn2预训练模型复现:数据准备、训练命令、日志分析与输出目录

Detectorn2预训练模型复现:数据准备、训练命令、日志分析与输出目录 在深度学习项目中,目标检测是一项重要的任务。本文将详细介绍如何使用Detectron2进行目标检测模型的复现训练,涵盖训练数据准备、训练命令、训练日志分析、训练指标以及训练输出目录的各个文件及其作用。特别地,我们将演示在训练过程中出现中断后,如何使用 resume 功能继续训练,并将我们复现的模型与Model Zoo中的

CSP-J基础之数学基础 初等数论 一篇搞懂(一)

文章目录 前言声明初等数论是什么初等数论历史1. **古代时期**2. **中世纪时期**3. **文艺复兴与近代**4. **现代时期** 整数的整除性约数什么样的整数除什么样的整数才能得到整数?条件:举例说明:一般化: 判断两个数能否被整除 因数与倍数质数与复合数使用开根号法判定质数哥德巴赫猜想最大公因数与辗转相除法计算最大公因数的常用方法:举几个例子:例子 1: 计算 12 和 18