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

素数素数和合数定义若\(p\in\Zeta\)，且\(p\not=0,\pm1\)，其约数集合中的元素只有\(1\)和\(p\)本身，那么称\(p\)为素数。若\(a\in\Zeta\)，且\(a\not=0,\pm1\)，\(a\)不为素数，则为合数。素数一般指正的素数。素数计数\(\pi(x)\)表示小于或等于\(x\)的素

题意原题链接求\(A^B\)的约数之和\(\bmod9901\)sol\(x\)的约数之和\(f(x)\)可以通过以下公式计算根据算数基本定理，将\(x\)分解为$$\prod_{i=1}^ka_i^{p_i}$$则$$f(x)=\prod_{i=1}^k\sum_{j=0}^{p_i}a_i^j=\prod_{i=1}^k\frac{a_i^{p_i+1}-1}{a_i-1}$$证明根据

题意原题链接求\(1\simn\)的约数个数和sol直接算很困难，考虑换一个角度求\(1\simn\)的约数个数和，等价于求\(1\simn\)分别是范围内几个数的约数对于第\(i\)个值，在\(1\simn\)中，存在\(i,2\cdoti,3\cdoti,\cdots,k\cdoti\)，共\(\lfloor\frac{n}{i}\rfloor\)因此，最终

前面是题解，后面是垃圾话T1Efim与奇怪的成绩贪心的找第一个可以四舍五入的，然后往上进位。T2BeautifulIPAddresses因为回文，所以\(n\ge7\)太长了，不合法，并且只用找一半，爆搜check即可。T3装饰结论题？发现两个上界：\(\frac{a+b+c}{3},a+b+c-\max(a,b,c)\)，答案就是两者中较

变形01背包#include<bits/stdc++.h>usingnamespacestd;constintN=1010;ints;intn,m;intv[N],w[N],f[N];intaccum(intp){//预先处理约数之和 intans=0; for(inti=1;i<=p-1;i++){//因为不包括它本身因此p-1;if(p%i==0)ans+=i;

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

首先这个约数公式要记住，具体见这篇题解然后剩下的就是比较简单的套路操作了，最后会化出来\[\sum_{d=1}^{min(n,m)}\sum_{d|x}\sum_{d|y}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rflooru(d)=\sum_{d=1}^{min(n,m)}u(d)(\sum_{d|x}\lfloor\frac{n}{x}\rfloor)(\sum_{d|y}\lf

原题链接：https://www.luogu.com.cn/problem/P1403题意解读：计算1~n每个数的约数个数之和。解题思路：1、数学方法1~n的约数范围也在1~n，要计算每个数的约数个数之和可以从约数出发，比如约数是x，那么在1~n中一共有n/x个数包含x这个约数x从1一直枚举到n，就可以得出每个约数是多少个

G.GCDonagridNotlongago,EgorlearnedabouttheEuclideanalgorithmforfindingthegreatestcommondivisoroftwonumbers.Thegreatestcommondivisoroftwonumbers$a$and$b$isthelargestnumberthatdividesboth$a$and$b$withoutleavinga

简单数论题求约数个数；本题需要用到质因数分解求约数个数，如果枚举一个一个求约数个数的话，你将会发现你已经喜提超时，见图1测试(图片）；#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+10;intf[N];intn;intsum;voidsolve(intx){intcnt=0;

3377.约数的个数(分解质因数)略试除法importjava.util.*;publicclassMain{privatestaticintcalc(intx){intres=0;for(inti=1;i<=x/i;i++){if(x%i==0){res++;if(i

寄的很惨T1[JLOI2014]聪明的燕姿https://gxyzoj.com/d/hzoj/p/3672敲个警钟，千万不要用一些奇怪的方法写自己会的题，不然大概率会一分不剩由小学奥数知识，约数和的求法为\(\prod(1+p_i^2+p_i^3+\dots+p_i^{a_i})\)所以，可以先线性预处理出约数和，再直接统计，时间复杂度\(O(nk)\)

本文用于个人算法竞赛学习，仅供参考目录一.质数的判定二.分解质因数三.质数筛1.朴素筛法 2.埃氏筛法3.线性筛法 四.约数1.求一个数的所有约数2.约数个数和约数之和3.欧几里得算法（辗转相除法）--求最大公约数一.质数的判定质数：质数是指在大于1的自然数中，除了1

题目链接EducationalCodeforcesRound139(RatedforDiv.2)D.LuckyChains取模的性质，更相减损术思路：我们假设链的长度为www，不妨设

​#include<bits/stdc++.h>//求约数和#include<map>usingnamespacestd;constintmod=1e9+10;typedeflonglongll;intmain(){ intn; cin>>n; unordered_map<int,int>primes; while(n--){ intx; cin>>x; for(inti=2

仅为了记录所学的知识.boolis_prime(intx){//求是否为素数 if(x<2)returnfalse; for(inti=2;i<=x/i;++i){ if(x%i==0)returnfalse; } returntrue;}voiddivide(intx){//分解质因子 for(inti=2;i<=x/i;++i){ ints=0; while(x%i==0)x/=i,s++; cou

frommathimportsqrtfromcollectionsimportCounter#①试除法求约数x=int(input())ans=[]foriinrange(1,int(sqrt(x))+1):ifx%i==0:ans.append(i)print(ans)#②求多个数乘积的约数个数n=int(input())a=[*map(int,input().s

题意求：\[\sum_{i=1}^n\sum_{j=1}^md(ij)\]其中\(d(n)\)代表\(n\)的约数个数。Sol考虑拆开\(d(ij)\)，平凡的想法是考虑\(i\)和\(j\)分别对\(d(ij)\)提供因子。注意到若\(i\)能提供完因子\(p\)，那么直接从\(i\)里取即可。否则需要在\(j\)里取因子

质数筛若一次判断很多数时，用到素数筛，将2～n没个数进行枚举，看哪些数是它的约数，将它乘上某个数(枚举倍数)：2i，3i···直到>n，未被标记(除本身无其他约数)即质数为什么是nlogn级别？看每个数枚举的次数，2大概\frac{n}{2}，3\frac{n}{3}···统一提n即有：n(\frac{1}{2}+\frac{1}{

0.前言积性函数是数论中一种极其重要的函数。它是指对于一个函数\(f(x)\)，如果\(\gcd(x,y)=1\)，则\(f(xy)=f(x)f(y)\)，则\(f(x)\)就是一个积性函数。积性函数大多数可以用线性筛质数的方法筛出来，本文将介绍几种常见的积性函数的筛法及一些拓展。1.线性筛质数大佬可跳

目录线性筛素数欧拉筛，老生常谈个人感觉放这道题的代码不如放板子//欧拉筛intprime[maxn];intfactor[maxn];intPrime(intn){intp=0;for(inti=2;i<=n;i++){if(!factor[i]){prime[p++]=i;factor[i]=i;

期望就是\(\sum序列长度\times这个长度的概率\)我们先想长为\(x\)的序列出现的概率为多大长度为\(i\)的序列，对于每个约数，约数集合为\(\sigma\)，出现概率为\(\sum_{p\in\sigma}(\frac{\lfloor\frac{m}{p}\rfloor}{m})^{i-1}\times\frac{m-\lfloor\frac

题面：记f(x)表示x的约数个数，例如，12的约数有1,2,3,4,6,12共6个，因此f(12)=6。给定n，求\(\sum_{k=1}^{n}k*f(k)\)。范围：n<=1E7思路：用类似素数筛的做法预处理出所有f，然后遍历一次得到答案，时间复杂度O(nloglogn)。#include<bits/stdc++.h>usingnamespacestd;#defineintlonglon

有两种做法第一种做法：欧拉反演（其实我赛时的时候是想到了欧拉反演的，但是我不太清楚欧拉反演的使用trick）欧拉反演的trick见这篇文章欧拉反演直接用在gcd上还是挺多的，可以想一下\(cnt\)数组怎么求\(cnt\)数组其实是只用记一维的（因为记两维肯定爆炸了）。考虑对于\(d\)，如果\(d\)不是