数论笔记-整除
目录整除整除的定义与基本性质素数素数的定义与基本性质素数判定试除法\(kn+i\) 法预处理法Miller-Rabin素性测试素数筛法埃氏筛欧拉筛（线性筛）反素数反素数的定义与基本性质枚举反素数正整数结构唯一分解定理质因子分解试除法Pollard-Rho算法因数因数的定义与基本性质正因数集合的求法试...
2018.12.31 NOIP训练 偶数个5（简单数论）
传送门对于出题人zxyoizxyoizxyoi先%\%%为敬题目需要龟速乘差评。题意简述：5e55e55e5组数据，给出n，请你求出所有n位数中有偶数个5的有多少，n≤1e18n\le1e18n≤1e18思路：一眼数位dpdpdp，哎哟这nnn怎么这么大绝望.jpg既然是zxyoizxyoizxyo...
UOJ #129 / BZOJ 4197 / 洛谷 P2150 - [NOI2015]寿司晚宴 （状压dp+数论+容斥）
题面传送门题意：你有一个集合 \(S={2,3,\dots,n}\)你要选择两个集合 \(A\) 和 \(B\)，满足：\(A \subseteq S\)，\(B \subseteq S\)，且 \(A \cap B=\varnothing\)不存在两个数 \(x \in A\)，\(y \in B...
最大公约数与扩展欧几里得算法[数论]
——!x^n+y^n=z^n 最大公约数（gcd）及其算法（欧几里得算法） 对于正整数 a，b 若存在c使得c|a且c|b，则称c为a，b的公约数，若c还满足a=pc，b=qc，且p，q互质，则称c为a，b的最大公约数，记为（a，b）。 当然我们可以用枚举的方法求gcd，但还有一种算法可以高效解决这...
【板子】数论基础（持续更新ing...）
#include<cstdio>#include<iostream>#include<cstring>#include<cmath>#include<algorithm>using namespace std;const int maxn=...
信息学中的一些些数论
因为本人数论较差，于是在noip前复习发现较大漏洞，特此作此篇记录一下。 一、逆元相关 首先我们先引入%运算 (a + b) % p = (a%p + b%p) %p （对） (a - b) % p = (a%p - b%p) %p （对） (a * b) % p = (a%p ...
2018.10.05 NOIP模拟 阶乘（简单数论）
传送门签到题。直接把所有数先质因数分解。同时统计每一个在阶乘中会出现的质数出现的最少次数。然后对于每一个这样的质数，我们求出满足其出现质数的m的最小值，然后求出所有m的最大值。求m的时候可以用二分求。代码...
洛谷P1368 均分纸牌（加强版） [2017年6月计划 数论14]
P1368 均分纸牌（加强版） 题目描述 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，纸牌总数必为 N 的倍数。可以在任一堆上取1张纸牌，然后移动。 移牌规则为：在编号为 1 堆上取的纸牌，能移到编号为 2和N 的堆上；在编号为 N 的堆上取的纸牌，能移到编号为 N-1和1...
洛谷P1621 集合 [2017年6月计划 数论13]
P1621 集合 题目描述现在给你一些连续的整数，它们是从A到B的整数。一开始每个整数都属于各自的集合，然后你需要进行一下的操作：每次选择两个属于不同集合的整数，如果这两个整数拥有大于等于P的公共质因数，那么把它们所在的集合合并。反复如上操作，直到没有可以合并的集合为止。现在Caima想知道，最后有...
CERC2017 F: Faulty Factorial 简单数论题
1 #include <iostream> 2 using namespace std; 3 #define ll long long 4 const int N = 10000006; 5 ll n,p,r; 6 ll poww(ll a,ll b){ 7 ...
CERC2017 F: Faulty Factorial 简单数论题
传送门：Faulty Factorial 分析： 分为n==p， n>=2*p, 2*p>n>p , n<p 四种情况讨论 其中n==p使用到了威尔逊定理,且注意， n=p=2，无解 情况不难想，看代码吧 #include <iostream>using n...
HDU 3818 A + B Problem 简单数论题
A + B Problem Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 458 Accepted Submission(s): ...
洛谷P1890 gcd区间 [2017年6月计划 数论09]
P1890 gcd区间 题目描述 给定一行n个正整数a[1]..a[n]。 m次询问，每次询问给定一个区间[L,R]，输出a[L]..a[R]的最大公因数。 输入输出格式 输入格式： 第一行两个整数n，m。 第二行n个整数表示a[1]..a[n]。 以下m行，每行2个整数表示询问区间的左右端点。 保...
求逆元的简单数论题
hdu 1576 A/B Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 691 Accepted Submission(s): 561 Pr...
HDU 1124 Factorial（简单数论）
Factorial Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1699 Accepted Submission(s): 1085...
洛谷P1390 公约数的和 [2017年6月计划 数论12]
P1390 公约数的和 题目描述有一天，TIBBAR和LXL比赛谁先算出1~N这N个数中每任意两个不同的数的最大公约数的和。LXL还在敲一个复杂而冗长的程序，争取能在100s内出解。而TIBBAR则直接想1s秒过而获得完胜，请你帮他完成这个任务。输入输出格式输入格式：共一行，一个正整数N。 输出格式...
2017第八届蓝桥杯省赛-大学B组 k倍区间(数论)
描述 给定一个长度为N的数列，A1, A2, … AN，如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数，我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗？ 输入 第一行包含两个整数N和K。(1 ...
poj1845 数论
//Accepted 204K 16MS //约数和 //n=p1^e1*p2^e2***pk^ek //约数和为:(p1^0+p1^1+..+p1^e1)*(p2^0+p2^1+..+p2^e2)*..(pk^0+pk^1+..pk^ek) //现考虑: S=p1^1+p1^2+.....
ACM数论之旅5---数论四大定理（你怕不怕(☆ﾟ∀ﾟ)老实告诉我）
（本篇无证明，想要证明的去找度娘）o(*≧▽≦)ツ----------数论四大定理---------数论四大定理：1.威尔逊定理2.欧拉定理3.孙子定理（中国剩余定理）4.费马小定理（提示：以后出现（mod p）就表示这个公式是在求余p的条件下成立）1.威尔逊定理：（PS：威尔逊是个厉害人）当且仅当...
hdu 3641 数论 二分求符合条件的最小值数学杂题
http://acm.hdu.edu.cn/showproblem.php?pid=3641学到：1、二分求符合条件的最小值/*==================================================== 二分查找符合条件的最小值==================...