博客主页：誓则盟约系列专栏：IT竞赛专栏关注博主，后期持续更新系列文章如果有错误感谢请大家批评指出，及时修改感谢大家点赞

原题链接题目描述给你一个整数数组nums。返回两个（不一定不同的）质数在nums中下标的最大距离。示例1：输入：nums=[4,2,9,5,3]输出：3解释：nums[1]、nums[3]和nums[4]是质数。因此答案是|4-1|=3。示例2：输入：nums=[4,8,2,8]输出：0解释：nums[2]是质

写在前面...通过写数论的md笔记，新知识不确定有没有学懂，但是我的md数学公式方法得到了极大的提升orz质数的定义：针对从2开始的整数定义，如果只包含1和本身这两个因数，则称该数为质数（素数）（1）质数的判定：试除法枚举因数的时候，只枚举到因数比较小的那个范围（根号n）（2）分解质因数：试除法从

思路对于这道题，我们可以发现一个事情：我们筛质数只需要筛\(1\sim\log_3n\)的部分就行了。因为\(k=p\timesq^3\)，那么，我们考虑一种极端情况，\(p\)为一个很小的数，那么\(k\)就无限接近于\(q^3\)。我们就先假设\(k=q^3\)，那么可以得出\(q=\log_3n\)。然后由题目描

题意：给出a和b(1<=b<=a<=5e6)，问a!/b!变成1，最多要经过多少轮？没轮可以选择一个它的因子来除它。思路：质因子数量，先线性筛，再质因子分解每个数，再前缀和，然后O1查询。总结：在模板中使用范围质数筛选时，当范围到了5e6就MLE了，没法弄，最后用的线性筛+质因子分解。考虑要不要为模板中单独

题目题目解析题目意思很简单，对于每一组数据来说，就是找这个偶数的两个质数相加的那两个质数，并且要满足加法中的第一个质数要是最小的质数，满足第一个质数是最小的质数的情况下也要保证第二个数也是质数代码#include<bits/stdc++.h>usingnamespacestd;boolis_prime(in

老年人过来对着会的题口胡几发B.腊肠披萨 题意翻译：给你n个小写字母串，求所有小写字母串两两之间的最长公共前缀的乘方和，对一个任意数取模。比较显然的，看到多串公共前缀直接建Trie统计贡献。建好之后对每个串在Trie上走，每走一步加上当前子树内串个数和父子树内串个数之差，就能

0.更新upd2023.5.21更新了关于powerfulnumber数量的证明upd2023.5.25更新了关于杜教筛的时间复杂度证明正文1.筛质数筛法其实就是判断质数的一个算法，但是是解决\([1,n]\)这一段区间的算法筛质数是最简单的一个用法1.1暴力最简单的方式就是对于每一个数去判断

注:\(\logx=\lnx\)组合基础加法原理、乘法原理排列数\(A^m_n=\frac{n!}{(n-m)!}\):从\(1\simn\)选\(m\)个数排成一列的方案数组合数\(C^m_n=\binom{n}{m}=\frac{n!}{(n-m)!m!}\):从\(1\simn\)选\(m\)个数的方案数。(相对于排列数不考虑顺序)

前言:本篇不太适合那些对数学证明要求严格的Oier，然后本人也是蒟蒻，主要写给自己回顾用的MillerRabin算法能快速的判断一个数是否为质数，作为一个数学算法它具有一定的玄学成分，但是在OI中通过一些手段可以使其达到100%正确。先让我们对比一下一般算法书教的2种关于质

相当Trivial的一篇东西。[ABC177E]Coprime给定\(n\)个数\(a_{1\simn}\)，值域为\(V\)。求：是否全部互质是否两两互质问题1：是否全部互质即求\(\gcd\limits_{i=1}^na_i\)是否为\(1\)。直接\(1\simn\)辗转相除求\(\gcd\)。时间复杂度\(O(n+\logV)\)。（

之前学习的的确是太浅薄了，于是重新学习一下。可以做什么？对于满足条件的积性函数\(f(n)\)，求其前\(n\)项和\(\sum_{i=1}^nf(i)\)。需要准备些什么？设\(N=\{x|x=\lfloor\frac{n}{i}\rfloor\}\)，即为所有整除的不同点值。设\(B=\sqrtn,p_{k}\)代表\(\leB\)的所有质

#include<stdio.h>#include<mpi.h>#include<malloc.h>#include<math.h>#include<string.h>booljud(inta){ intk=0; if(a<=1) returnfalse; for(inti=2;i<pow(a,0.5)+1;i++){ k=a%i; if(k==

质数试除法判定质数boolprimes(intx){  if(x<2)returnfalse;  for(inti=2;i<=x/i;i++){    if(x%i==0)returnfalse;  }  returntrue;}埃筛1intp[N],k,n;boolf[N];voidprimes(intn){//埃筛，思想：质数的倍数是合数for(inti

描述已知正整数 n 是两个不同的质数的乘积，试求出较大的那个质数。输入描述输入只有一行，包含一个正整数 n。输出描述输出只有一行，包含一个正整数 p，即较大的那个质数。用例输入1 21用例输出1 7提示【数据范围】对于 60%的数据， 6≤n≤1000。 对于 1

乘法逆元若\(a\timesb\equiv1(\bmod\c)\)，且\(\gcd(a,b)=1\)，那么我们定义\(a\)为\(b\)的逆元，也可以称\(a\)是\(b\)在\(\bmod\c\)意义下的倒数。费马小定理对于质数\(p\)和任意整数\(a\)，有\(a^p\equiva(\bmod\p)\)。反之，若\(a^p\equiv

一般函数\(\times\)一般函数\(O(n\logn)\)暴力即可，\(O(n\logn)\)一般函数\(\times\)积性函数\(O(n\log\logn)\)对每一个指数跑类似FWT的东西，\(O(n\log\logn)\)积性函数\(\times\)积性函数\(O(n)\)如果我们能把每一个质数\(p^a\)的答案得到，我们就能欧拉筛

前置知识Cpp实现基础算法//basemethodboolbasement(intnum){ for(inti=2;i<=sqrt(num);++i) { if(num%i==0) returnfalse; } returntrue;}证明筛法初步根据初等数学的知识，如果一个数不是2的倍数，那么它肯定不是2的倍数的倍数，所以，进一步的

赛氪OJ-专注于算法竞赛的在线评测系统(saikr.com)题目描述小明在学校学了质数和合数的知识后，便想知道对于任意的一个数N，将其拆分为一个质数与一个合数相加的结果，有几种拆法？但后来想想又觉得太简单了，于是他追加了一些条件，合数要继续拆分为两个数相乘的形式才行，那么满足以上

1405：质数的和与积时间限制:1000ms内存限制:65536KB提交数:31481通过数:23479【题目描述】两个质数的和是S，它们的积最大是多少？【输入】一个不大于10000的正整数S，为两个质数的和。【输出】一个整数，为两个质数的最大乘积。数据保证有解。【输入样例】50

欧拉函数\(\varphi\)的定义，\(\varphi(i)\)表示从\([1,i]\)之间和\(i\)互质的数的数量（\(a\)和\(b\)互质即\(\gcd(a,b)=1\)）。欧拉函数是积性函数，例如\(a,b\)都为质数，那么\(φ(ab)=φ(a)\timesφ(b)\)，递推式为\[φ(ab)=\frac{φ(a)\timesφ(b)\times

一、欧拉函数定义\([1,n]\)中与\(n\)互质的数的个数，称为欧拉函数，记为\(\varphi(n)\)。互质的定义：对于正整数\(a\)和\(b\)，若\(gcd(a,b)=1\)，则\(a\)和\(b\)互质。性质若\(p\)是质数，则\(\varphi(p)=p-1\)。证：因为\(p\)是质数，所以因数只有\(1\)和\(p\)。

一、算法简析线性筛，又叫欧拉筛，用来筛出\([2,n]\)中所有的质数。该算法比埃氏筛的效率更高，为线性\(O(N)\)。该算法也是从小到大枚举每个数，若该数没筛掉，则为质数。但是，筛数的规则不同：此时枚举的数是\(i\)，无论是否是质数，枚举已知的质数\(p_j\)，合数\(i*p_j\)未越界，即不大

题目大意：求区间\([l,r]\)中有多少正整数满足\(\phi(\phi(n))=\phi(n)-1\)，其中\(\phi\)为欧拉函数。解：设\(y=\phi(n)\)，则上式变为\(\phi(y)=y-1\)，易证\(y\)为质数（注意\(\phi(1)=1\)，\(1\)与任何正整数都互质）。故原问题转化为求\([l,r]\)中有多少个正整数v满足\(\phi

数学相关最大公约数模板intgcd(inta,intb){ intx=a%b;while(x){a=x;a^=b^=a^=b;x=a%b;}returnb;}最大公倍数模板intlcm(inta,intb){returna*b/gcd(a,b);}质数相关确定是不