scala
golang
jmeter
程序员
java8新特性
pdf
虚函数表和虚表指针
dcl语言
共享充电桩小程序
51单片机
滤波
链接
P3C
比较两个宽字符串的字符
大学生网页作业
torch
App应用程序
MACD策略
大学生志愿者
docker 搭建es7
数论
2024/4/11 22:24:35![「欧拉定理」[SDOI2008]仪仗队](https://img-blog.csdnimg.cn/img_convert/6e21f1e1efc4be1c3f6f034ba8e38b9e.png)
「欧拉定理」[SDOI2008]仪仗队
[SDOI2008]仪仗队 https://ac.nowcoder.com/acm/problem/20313 题目描述
作为体育委员，C君负责这次运动会仪仗队的训练。
仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所…
两数平方和定理，勒让德三平方和定理，拉格朗日四平方和定理
婆罗摩笈多－斐波那契恒等式
婆罗摩笈多－斐波那契恒等式(Brahmagupta–Fibonacci identity): (a2b2)(c2d2)(ac−bd)2(adbc)2(acbd)2(ad−bc)2\begin{aligned} \left(a^2 b^2\right)\left(c^2 d^2 \right) & \left(ac - bd \right)^2 \left(ad bc…
第十周周赛——周赛兼组队赛第二场题解（出自 BNUOJ28207，BNUOJ28201，BNUOJ28209，codeforces 667B，HDU 5439，HDU 5478）
A题：
A题题目链接
题目描述： Star TimeLimit: 1000ms MemoryLimit:32768KB64-bit integer IO format:%I64dProblem DescriptionOverpower often go to the playground with classmates. They play and chat on the playground. One day, there are a…
![bzoj 4475: [Jsoi2015]子集选取](http://www.lydsy.com/JudgeOnline/upload/201604/11%282%29.png)
bzoj 4475: [Jsoi2015]子集选取
Description Input 输入包含一行两个整数N和K，1<N,K<10^9 Output 一行一个整数，表示不同方案数目模1,000,000,007的值。 Sample Input 2 2 Sample Output 16其实这题原题还有一组样例6 40，输出是401898087然后手推找规律可以发现答案就…
codeforces 963A/964C Alternating Sum【数学】
题目大意：给你一个n,a,b,k 有n1个数据，让你求∑ni0sian−ibi∑i0nsian−ibi答案取模1e99 条件是这n1个数据每k个是一个循环 1<n,a,b<1e91<n,a,b<1e9, 1<k<1e51<k<1e5题目分析 如果我们让第ik项比上第i项就可以发下只剩下 bk/…
Algorithm Review 3.2 数论
质因数分解
Miller Rabin 素性测试
根据费马小定理，我们能够得出一种检验素数的思路（即费马素性测试）： 验证 ∀ 1 < a < n , a n − 1 ≡ 1 ( m o d n ) \forall 1 < a < n, a^{n - 1} \equiv 1(\mod n) ∀1<a&…
51nod 中国剩余定理
看了好久，才发现原来自己曾经用过的方法，这只是一种推广。
就是单因子勾件法。每次找到能被其中一个除数除剩一，能被其他整除的数。最后加起来，然后对总和求余。
#include<cstdio>
#include <iostream>
#include …
题232.pat甲级练习-1059 Prime Factors (25 分)
文章目录题232.pat甲级练习-1059 Prime Factors (25 分)一、题目二、题解题232.pat甲级练习-1059 Prime Factors (25 分) 一、题目 二、题解 #include <bits/stdc.h>using namespace std;const int maxn1000000;int cnt;
int p[maxn],vis[maxn];void isPrime(int n)//这里…
向量的数量积，向量积，混合积及应用
http://wenku.baidu.com/link?urlvKzZSSrCdYbfej5dfWZOFOzahSoQoO8SoC1RC7XCHVvDWZEhw7lFj76qzAx2hWDTMDfccbp4pBbZfOCNt57o-kVB1xD6z3vWVh9GCO-g01K (百度文库详解) 简单的总结一下： 一：数量积(点积，点乘，内积) a b ÿ…
Count the Buildings （Stirling数）
题意：n个建筑高度为1-n,从前能看到f个，从后能看到b个，求可能有多少张排序情况
解析：最高建筑n是一定可以看到的，固定住最高建筑n号楼的位置，将n号楼左边分为f-1组，右边b-1组，且用每…
C# 求3个数的最大公约数数之数论革命
相关导读：
C# 求3个数的最小公倍数之数论革命
https://blog.csdn.net/number1killer/article/details/88570957
C# 求3个数的最小公倍数之代数革命
https://blog.csdn.net/number1killer/article/details/88570888
Java求三个数的最小公倍数算法改进࿰…
扩展欧几里德模板及讲解
转载请注明出处，谢谢合作。 http://blog.csdn.net/fanhansheng/article/details/52743669
对于形如”AxByC”的式子，求二元一次不等式的一组特解。令m gcd(a, b); 其存在解的条件为C为A和B最大公约数的整数倍。
推导:
bx (a%b)y gcd(b, a%b); —…
牛客题单——同余、并查集
题单链接
Strange Way to Express Integers（表示整数的奇怪方式）
这道题之前已经写过了，不重复写了，下面是链接 中国剩余定理
程序自动分析
这道题很明显是用并查集解决的 如果两个数相等，就把两个数放入一个集合中…
约数个数和约数之和算法总结
知识概览
约数个数 基于算数基本定理，假设N分解质因数的结果为 可得对于N的任何一个约数d，有 因为N的每一个约数和~的一种选法是一一对应的，根据乘法原理可得， 一个数的约数个数为 约数之和 一个数的约数之和公式为 多项式乘积的…
51nod N的阶乘的长度 V2（斯特林近似）斯特林近似公式
输入N求N的阶乘的10进制表示的长度。例如6! 720，长度为3。 Input第1行：一个数T，表示后面用作输入测试的数的数量。（1 < T < 1000)
第2 - T 1行：每行1个数N。（1 < N < 10^9) Output共T行&…
第九周周赛——周赛兼组队赛第一场题解（出自HDU5443，本oj，HDU 5667，poj1742，codeforces 664A，BUNOJ 28199）
A题：
A题题目链接
题目描述： The Water Problem TimeLimit:1000MS MemoryLimit:131072KB64-bit integer IO format:%I64dProblem DescriptionIn Land waterless, water is a very limited resource. People always fight for the biggest source of …
第0周周赛——极限手速赛（题解）之下篇
J题：
J题题目链接
题目描述： 给定一个数n，问你在[1,n]之间有多少个数能够整除[2,10]中所有的数（对，你没看错，是所有哦） Input输入只有一行，包含一个整数n (1 ≤ n ≤ 1018) O…
AT2000 [AGC002F] Leftmost Ball 题解
AT2000 [AGC002F] Leftmost BallAT2000 [AGC002F] Leftmost Ball 感觉转移还是挺难的。OrzAK_STAR\color{white} Orz\ AK\_STAROrz AK_STAR 我们不妨考虑随便染色，对于一种合法的染色肯定是对于任意前缀和白色的数量都大于等于颜色的数量。
那么我们不妨考虑通过白…
C# 快速模指数运算 快速求余运算
此方法解决这样一个问题，就是a^b mod m 的余数是多少。
如果直接计算a^b，方次很大的时候，会溢出，而且时间很长。
当然指数很小的时候直接用自带的Math函数就行，如果指数很大的时候，可以用以下的方法。
原…
C# 给出3个数求其中任意2个数的最大公约数
相关导读：
Java求三个数的最小公倍数算法改进（化境）
https://blog.csdn.net/number1killer/article/details/84143490
Java求三个数的最小公倍数算法优化
https://blog.csdn.net/number1killer/article/details/84107757
Java求3个数的最…
【算法】Partitioning the Array（数论）
题目
Allen has an array a1,a2,…,an. For every positive integer k that is a divisor of n, Allen does the following: He partitions the array into n/k disjoint subarrays of length k. In other words, he partitions the array into the following subarrays: [a1,…
扩展欧几里德算法详解 以及模线性方程最小整数解 例： POJ -1061青蛙的约会
要彻底理解扩展欧几里德算法(递归实现)需要知道以下几个知识点： 欧几里德算法的原理 递归的回溯 贝祖等式
1.欧几里得算法的证明： 欧几里德算法是用来求两个数的最大公因数，其根本思想是gcd(a,b) gcd(b,a%b 文字表达就是 a 和 b 的最大公…
[51nod2026]Gcd and Lcm
Description
已知f(n)∑d|nμ(d)d求∑i1n∑j1nf(gcd(i,j))f(lcm(i,j))n<1e9Solution
一眼以为f是φ我是不是没救了QwQ 但是这并不妨碍我们发现f是积性函数 然后把lcm(i,j)写成ij/gcd(i,j)，易知i/gcd(i,j)与j互质，gcd(i,j)与i/gcd(i,j)互质 所以f…
POJ 1601 青蛙的约会
题意是两只青蛙，一开始分别在x，y点，他们分别每单位时间可以移动m，n个点位时间，路径是一个单位长度为l的圆环
通过题意很容易得到一个方程：
（n-m）*kt*lx-y;
其中k和t是未知数&…
C# 求3个数的最大公约数之返璞归真
相关导读：
C# 求3个数的最小公倍数之代数革命
https://blog.csdn.net/number1killer/article/details/88570888
Java求三个数的最小公倍数算法改进（化境）
https://blog.csdn.net/number1killer/article/details/84143490
Java求三个数的最小公倍数算法优化
https://bl…
CodeForces Hello 2019 1097D - Makoto and a Blackboard(积性函数)
首先设EEE是一阶期望，显然有下式成立,这说明EEE是积性函数. E(n)σ(n)d(n)∏pa∥n1p⋯paa1∏pa∥nE(pa)E(n)\frac{\sigma(n)}{d(n)}\prod_{p^a \Vert n} \frac{1p\dots p^a}{a1}\prod_{p^a\Vert n} E(p^a) E(n)d(n)σ(n)pa∥n∏a11p⋯papa∥n∏E(pa) 其次假…
关于欧拉函数的一个性质
昨天，有一个人过来问我，如何证明∑d|nϕ(d)n毫无头绪，一群人乱搞乱搞，一个晚上都没证出来。于是决定组队去请(bei)教(diao)PhilipsWeng大犇。大犇愣了三秒（注意，3s），然后给出了一种高…
《洛谷深入浅出进阶篇》同余方程+中国剩余定理——洛谷P1495
这篇文章讲介绍：同余方程，中国剩余定理
什么是同余方程？
xy （mod p）这样的，带同余号的式子就是同余方程。
什么是中国剩余定理？
中国剩余定理，顾名思义是出自中国，它…
蓝桥杯 1223 第 2 场 小白入门赛
蓝桥小课堂-平方和
模拟 1 2 2 2 3 2 ⋯ n 2 n ⋅ ( n 1 ) ⋅ ( 2 n 1 ) 6 1^22^23^2\cdotsn^2\dfrac{n\;\cdot\;(n 1)\;\cdot\;(2n1)}{6} 122232⋯n26n⋅(n1)⋅(2n1)。 write(n * (n 1) * (n * 2 1) / 6);房顶漏水啦 m a x ( 最大的行 − 最小的行 , 最大的列 −…
bzoj 1465: 糖果传递
Description 老师准备了一堆糖果, 恰好n个小朋友可以分到数目一样多的糖果. 老师要n个小朋友去拿糖果, 然后围着圆桌坐好, 第1个小朋友的左边是第n个小朋友, 其他第i个小朋友左边是第i-1个小朋友. 大家坐好后, 老师发现, 有些小朋友抢了很多的糖果, 有的小朋友只得到了一点点糖…
【NOIP2013模拟联考6】选课(select)
Description
求1~n的排列中，i不放在i和i1且n不放在1的方案数。 n<10^5
Solution
容斥原理乱搞。 表示蒟蒻只能看题解了。。。 我们设W(k)表示至少有k个位置不合法的方案数。 那么，我们把每个位置要选的按顺序写下来，得到了1,2,2,3,…
[LOJ#6053]奇怪的函数
Description
给出一个函数f(x)满足： f(1)1, f(p^c)p xor c,p是质数 f(ab)f(a)*f(b),(a,b)1 求∑ni1f(i)对1e97取模 n<1e10
Solution
min_25筛例题 不会可以看一下神仙zzq的博客 我们只需要知道所有质数的f(x)之和，显然指数都为1，…
Codeforces Round 893 (Div. 2)ABC
Codeforces Round 893 (Div. 2) 目录 A. Buttons题目大意思路核心代码 B. The Walkway题目大意思路核心代码 C. Yet Another Permutation Problem题目大意思路核心代码 A. Buttons 题目大意
一共有三个盒子分别是a、b、c，第一个人只能拿a、c，第二个人只…
Codeforces Round 913 (Div. 3)ABCDEF
文章目录 A. Rook题目题目大意思路核心代码 B. YetnotherrokenKeoard题目题目大意思路核心代码 C. Removal of Unattractive Pairs题目题目大意思路核心代码 D. Jumping Through Segments题目题目大意思路核心代码 E. Good Triples题目题目大意思路核心代码 F. Shift and Rever…
剑指offer.C++ 浅析BSGS算法
前言
数论大法好，人间真善美。。。 BSGS算法
一般用来求解成立的最小的L的解
对于求解这道题，要先进行分解
设 L i * x - y ，就得到 ，即
再移项 然后就是循环一遍 y 的值，将其存入HASH表中
在循环枚举 i &#…
浅析中国剩余定理（CRT）
中国剩余定理
用来求解同余方程组的最小非负整数解，其中 都互质 首先让 M 等于所有 的最小公倍数，对于求解每一个的方程
先设一个 ，再求解其逆元 则会有一组最小解
其通解就是
如果没有看懂，可以看详细求解同余方程这一篇博…
2018 BUPT Winter Training #5 Div.2
A - 解方程
看着吓人，实则low得一比，就是求(a,b)到(c,d)的距离。
#include <cstdio>
#include <cmath>
using namespace std;
double dis(double x1,double y1,double x2,double y2){return sqrt((x1-x2)*(x1-x2)(y1-y2)*(y1-y2));
}
int …
C++ 二元一次不定方程巧妙求解——运用扩展欧几里得算法
前言
在关于数论的学习中，求解二元一次不定方程是很重要的，在学习求解二元一次不定方程之前，要先了解欧几里得算法和扩展欧几里得算法。
关于数论的学习 欧几里得算法
欧几里得算法就是辗转相除法，欧几里得算法中 ( x , y ) 的…
bzoj 2301: [HAOI2011]Problem b
Description 对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) k，gcd(x,y)函数为x和y的最大公约数。 Input 第一行一个整数n，接下来n行每行五个整数，分别表示a、b、…
青蛙的约会 （同余）
题意：两只青蛙在同一纬度上（就是圆圈上）不同位置，具有不同的速度，看几次能跳的一起
解析：设经过t次调到一起，(xm*t）mod L(yn*t) mod L
上式整理一下 (xm*t)-(yn*t)p*L;(p是两只青…
POJ 1061 青蛙的约会 扩展欧几里德- 猪都懂啦 = =
青蛙的约会 Time Limit: 1000MS Memory Limit: 10000KB 64bit IO Format: %lld & %llu Submit
Status Description 两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它…
高斯消元法解线性方程组
高斯消元法
这种方法，可以在接近O(n3)的复杂度下求解线性方程组，忧郁克拉默法则的O(n*n!)
对于一组线性方程组，枚举每一列进行如下步骤： 1、找到绝对值最大的一行 2、将这一行交换到第一行 3、将这一行的第一个数变成1ÿ…
关于欧拉函数积性的问题
Proposition 若(m,n)1\text{Proposition 若}(m,n)1Proposition 若(m,n)1,那么φ(mn)φ(m)φ(n).\varphi(mn)\varphi(m)\varphi(n).φ(mn)φ(m)φ(n). 首先中国剩余定理断言 x≡a(modm)x≡b(modn)\begin{array}{cc}x\equiv a& \pmod{m}\\x\equiv b& \pmod{n}\en…
C++ 数论学习 质因数分解 —— 无关的元素
引言
数论大法好，人间真善美。。。 题目 题目描述 对于给定的n个数a1，a2，...，an，依次求出相邻两数之和，将得到一个新数列。重复上述操作，最后结果将变成一个数。问这个数除以m的余数与哪些数无…
C# 求3个数的最大公约数之便捷算法
在之前算法的基础上增加了一些便捷算法：
相关导读：
C# 求3个数的最大公约数之返璞归真
https://blog.csdn.net/number1killer/article/details/104615730
C# 求3个数的最小公倍数之代数革命
https://blog.csdn.net/number1killer/article/details/88570888
Java求三个数…
求3个数的最小公倍数算法之数论细化（C# ）
求3个数的最小公倍数之算法研究集成（C# ）
https://blog.csdn.net/number1killer/article/details/104637856
求3个数的最小公倍数之便捷算法（C# )
https://blog.csdn.net/number1killer/article/details/104681168
求3个数的最大公约数之算法研究集成（C#）
https://bl…
Reduced ID Numbers （同余）
题意：给出几个数 ，寻找一个最小数使这几个数mod它的值不相同
解析：暴力枚举从1开始，将模完的数保存在一个数组里，如果遇到相同的值，就增大值继续枚举。直到寻找到。
此处使用了mod[]数组，将模…
三个重要的同余式——威尔逊定理、费马小定理、欧拉定理 + 求幂大法的证明
转自：http://blog.csdn.net/synapse7/article/details/19610361
一、威尔逊定理
若p为质数，则
p|(p-1)!1
亦：(p-1)! ≡ p-1 ≡ -1(mod p) 例题：
HDU 2973 YAPTCHA (威尔逊定理及其逆定理)
解题报告见http://blog.csdn.net/s…
1G - Maximum Subrectangle
You are given two arrays aa and bb of positive integers, with length nn and mmrespectively.
Let cc be an nmnm matrix, where ci,jai⋅bjci,jai⋅bj.
You need to find a subrectangle of the matrix cc such that the sum of its elements is at most xx, and its ar…
2023河南萌新联赛第（六）场：河南理工大学
目录
A 简单的异或
题目：
解析：
B 这是dp题吗
题目链接：https://ac.nowcoder.com/acm/contest/63602/B
解析：
D 买饼干的小Y
题目：https://ac.nowcoder.com/acm/contest/63602/D
解析：
E 不爱吃早…
hdu 6209 The Intersection
Problem DescriptionA given coefficient Kleads an intersection of two curves f(x)and gK(x). In the first quadrant, the curve fis a monotone increasing function that f(x)x−−√. The curve gis decreasing and g(x)K/x.To calculate the x-coordinate of the only …
bzoj 2440: [中山市选2011]完全平方数
Description 小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些 数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而 这丝毫不影响他对其他数的热爱。 这天是小X的生日，小 W 想送一个数给他作为生日礼…
【NOIP2015模拟11.2晚】Lala买面包
Description
给出n个数，求这n个数中有多少个数可以写成x^p（x>2,p>2）的形式。 n<10^6 每个数<10^14
Solution
很容易想到枚举指数。 一个明显的性质，指数只可能是质数，且最大为50. 那么我们可以直接…
Saving Beans (卢卡斯定理)
题意：在n棵树上摘不超过m个豆子的方案数
考虑多加一棵树，这样的话多加的那棵树摘了k个豆子时，原本n棵树上的豆子数量之和就等于m-k，满足题目要求，也降低了计算的难度。
则题目要求a1a2a3a4........anan1m; 解有多少…
数论 整除理论(1)
Problem Problem 设奇数n>1n>1，证明：nn是素数的充分必要条件是n" role="presentation" style="position: relative;">nn不能表为三个或三个以上的连续正整数之和。 解： 必要性： 设自然数前缀…
Codeforces 1027G X-mouse in the Campus
(Codeforces 1027G)(Codeforces 1027G)考虑两个整数1⩽m,n⩽1014,(m,n)1,1⩽m,n⩽1014,(m,n)1,问若定义等价类x{a|amkx,a∈Zn}x{a|amkx,a∈Zn},这样的等价类有多少个？ 记M⟨m,⋅n⟩M⟨m,⋅n⟩,由欧拉定理mφ(n)≡1mφ(n)≡1且(m,n)1,(m,n)1,这是一个φ(n)φ(n)阶循…
[51nod1362]搬箱子
Description
一个n*m的棋盘，每一步可以从(x,y)走到(x,y1)或(x1,y)或(x1,y1). 求从(0,0)走到最后一行的方案数，答案对p取模。 n<800，m,p<10^9
Solution
显然可以枚举斜走的步数。 然后再枚举走到(n,j)，我们要有梦想这个…
Min_25筛学习小记
前言
从神仙zzq的博客中学来的科技，似乎可以全面吊打洲阁筛？？（反正我不会） 设F(x)是一个积性函数，我们需要求出∑i1nF(i)Min_25
并不知道为什么要叫Min_25筛 我们首先需要求出所有F(pj)的和，…
判断质数和用算数基本定理分解质因数
文章目录摘要质数判断一个数是否是质数分解质因数超级详细的基础算法和数据结构合集：https://blog.csdn.net/GD_ONE/article/details/104061907摘要
本文主要讲解如何判断一个数是质数，和如何对一个数分解质因数。本文是很基础的也很重要的数学知识。
…
素数筛法详解：埃氏筛和欧拉筛
文章目录摘要埃式筛欧拉筛超级详细的基础算法和数据结构合集： https://blog.csdn.net/GD_ONE/article/details/104061907
摘要
本文主要介绍埃氏筛法和欧拉筛法。 之前讲了怎么判断一个数是不是质数，现在求区间[1,1e7][1, 1e7][1,1e7]内所有的质数。我…
Find a multiple （鸽巢原理）
题意：给你n个数，从中选取m个数的和是n的倍数，（只输出一个就可以）
解析：
ps:
鸽巢原理：n1的物体放到n个盒子里，至少有一个盒子放了两个物体。
Sk表示a1a2……ak,如果Sk是n的倍数&…
求3个数的最小公倍数算法之数论进化
求3个数的最小公倍数算法之数论再细化
https://blog.csdn.net/number1killer/article/details/104902304
求3个数的最小公倍数之便捷算法（C# )
https://blog.csdn.net/number1killer/article/details/104681168
求3个数的最大公约数之算法研究集成（C#）
https://blog.cs…
Codeforces Round 926 (Div. 2)（A,B,C,D,E,F）
这场还是很有含金量的，B题开始就有难度了，B是个推结论的题，C要推结论然后递推，D题是有点难的树上DP（主要是状态转移方程不好写），E题是个二进制预处理然后状压DP，F题是个数论…
快速乘法技巧：Karatsuba, Toom, Good, Schonhage, Strassen, Nussbaumer
参考文献：
[Ber01] Bernstein D J. Multidigit multiplication for mathematicians[J]. Advances in Applied Mathematics, 2001: 1-19.FFT/NTT：以 CRT 的视角 文章目录 Map & LiftMappingLifting Karatsuba’s trickToom’s trickFFT trickGood’s…
阶乘约数+猴子分香蕉（蓝桥杯JAVA解法）
阶乘约数：用户登录
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
定义阶乘 n!123⋅⋅⋅n。
请问 100!（100 的阶乘）有多少个正约数。
运行限制
最大运行时间：1s…
《洛谷深入浅出进阶篇》P5091 —— 扩展欧拉定理，快读取模。
P5091 【模板】扩展欧拉定理 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P5091 大概题意：给出三个正整数，a，m，b 你需要求出 的值，其中 首先求出m的欧拉函数,由欧拉定理可知&#…
214. Devu和鲜花
214. Devu和鲜花 - AcWing题库 如果每个盒子里的花的数量是无限的，用隔板法可以得出答案是
现在每个盒子中区的花数要满足n个条件
我们可以求答案的补集，用全部方案数减去补集方案数
每一个不符合条件的要求为，设为Bi
补集方案数为就成了…
牛客题单——贪心、数论
题单链接
反素数
反素数就是一个数的因子大于所有小于这个数因子的数
题目中要求的区间内的最大反素数 等价于 求这个区间内因子最多的数且这个数最小 可以用反证法进行证明： 假设在当前区间中的答案是x，如果y的约数个数大于x，那么x就不是…
小凯的疑惑构造性证明
如有谬误，欢迎联系 premierbobqq.com，笔者感激不尽。 “小凯的疑惑”中的核心命题 ∀n>ab−a−b,∃p,qs.t.npaqb\forall n>ab-a-b,\exist p, q\;s.t.\;npaqb ∀n>ab−a−b,∃p,qs.t.npaqb
其中，a,ba, ba,b 为一对互质的整数&#x…
Leetcode.2601 质数减法运算
题目链接 Leetcode.2601 质数减法运算 Rating ： 1779 题目描述
给你一个下标从 0 开始的整数数组 nums，数组长度为 n 。
你可以执行无限次下述运算：
选择一个之前未选过的下标 i ，并选择一个 严格小于 nums[i]的质数 ppp &…
剑指offer.C++数论 gcd 巧解——运用 欧式筛法欧拉函数 快速求解
前言
数论大法好，人间真善美。。。 题目描述
给定整数N，求1<x,y<N且Gcd(x,y)为素数的数对（x,y）有多少对？
输入
一个整数
1<N<1000000
输出
一个整数
样例输入
4
样例输出
4
提示
【样例解释】…
牛客国庆集训派对Day4 E 乒乓球【公式+ntt】
题目：小 Bo 是某省乒乓球名列前茅的选手，现在他有 n 颗乒乓球一字排开，第 i 颗乒乓球的权值为 wi 每次他会随机从现有的乒乓球中等概率选一颗拿走，然后得到的收益是这颗球左边第一个乒乓球和右边第一个乒乓球的权值的乘积…
选自《洛谷深入浅出进阶篇》——欧拉函数+欧拉定理+扩展欧拉定理
欧拉函数：
欧拉函数定义： 1~n中与n互质的数的个数。 比如 欧拉函数是积性函数：（也就是）当 n与m互质的时候： 由算术基本定理，我们可以设n，那么我们只要计算出的取值就能求出的取…
acwing算法基础之数学知识--中国剩余定理
目录 1 基础知识2 模板3 工程化 1 基础知识
中国剩余定理的内容如下：
已知整数 m 1 m_1 m1、 m 2 m_2 m2、… m k m_k mk两两互质，则对于任意的整数 a 1 a_1 a1、 a 2 a_2 a2… a k a_k ak，方程组 { x ≡ a 1 ( m o d m 1 ) x …
第0周周赛——极限手速赛（题解）之上篇
A题：
A题题目链接
题目描述： 这道题是一血 TimeLimit:500MS MemoryLimit:64MB64-bit integer IO format:%I64dProblem Description什么？这道题竟然没有题目描述？ Input输入只有一行，包含一个整数n (2 ≤ n ≤ …
【蓝桥杯】历届试题 连号区间数（数论）
历届试题 连号区间数
问题描述 小明这些天一直在思考这样一个奇怪而有趣的问题： 在1~N的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是： 如果区间[L, R] 里的所有元素（即此排列的第L个到第R个元素）递增…
【QED】高昂的猫 Ⅰ
目录 题目背景题目描述输入格式输出格式 测试样例样例说明数据范围 思路核心代码 题目背景 这是小橘。因为它总是看起来很高傲，所以人送外号“高昂的猫”。
题目描述
"锕狗"的房间里放着 n n n ( 1 ≤ n ≤ 1 0 9 ) (1 \leq n \leq 10^9) (1≤n≤109)个…
KK's Steel bestcoder round 71 hdu 5620（裴波那契）
Problem Description Our lovely KK has a difficult mathematical problem:he has a N\left( 1\leq N\leq {10}^{18}\right)N(1≤N≤10 18 ) meters steel,he will cut it into steels as many as possible,and he doesn’t want any two of them be the same lengt…
215. 破译密码 - mobius函数 + 整数分块
215. 破译密码 - AcWing题库 mobius函数：
一个数的分解质因数形式，某一个指数>1为0，质因数为奇数个为-1，偶数个为1
mobius函数可以与容斥结合起来，比如mobius[2] -1, mobius[3] -1, mobius[2 * 3] 1。对应容斥…
P2558 [AHOI2002] 网络传输提交，位运算，高精度
P2558 [AHOI2002] 网络传输 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
在计算机网络中所有数据都是以二进制形式来传输的。但是在进行较大数据的传输时，直接使用该数的二进制形式加以传输则往往传输的位数过多。譬如要传输 1024 就需要 11 位二进制…
牛客寒假算法基础集训营5_G炫酷数字（因数）
题目链接：https://ac.nowcoder.com/acm/contest/331/G
题目描述:
小希希望你构造一个最小的正整数，使得其有n个因子。
输入描述:
第一行一个整数T表示数据组数
每组数据第一行输入一个正整数n，表示其因子数。
n≤1,000,000n≤1,000,000…
【c++】分蛋糕（数论）
分蛋糕
题目难度：简单
时间限制：1024ms
内存限制：128mb
题目描述
把一块 m 厘米 * n 厘米的蛋糕分割成同样大的正方形，如果要求没有蛋糕剩余，分割出的正方形蛋糕最大边长是多少厘米？（最少不…
B3716 分解质因子 3
#include <bitset>
#include <vector>
#include <iostream>
#include <algorithm>const int maxn 100000008;std::vector<int> prm, pre; // pre is the min-factor array.
bool np[maxn];void getPrime(const int N 100000000) {//线性筛&am…
蓝桥杯AcWing学习笔记 8-2数论的学习（下）
蓝桥杯
我的AcWing
题目及图片来自蓝桥杯C AB组辅导课
数论（下） 蓝桥杯省赛中考的数论不是很多，这里讲几个蓝桥杯常考的知识点。 约数个数定理
我们如何去求一个数的约数个数呢？ N N N分解质因数的结果： N P 1 α…
《洛谷深入浅出进阶篇》p2568 GCD
P2568 GCD - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P2568 大致题意：给定正整数n，求1< x,y<n 且 gcd（x，y）为素数的数对（x，y）有多少对。…
蓝桥杯AcWing学习笔记 8-1数论的学习（上）
蓝桥杯
我的AcWing
题目及图片来自蓝桥杯C AB组辅导课
数论（上） 蓝桥杯省赛中考的数论不是很多，这里讲几个蓝桥杯常考的知识点。 欧几里得算法——辗转相除法 欧几里得算法代码：
import java.util.Scanner ;public class Main…
十一届蓝桥杯研究生组国赛-循环小数(数论)
十一届蓝桥杯研究生组国赛-循环小数 1、题目描述2、解题思路3、代码实现1、题目描述 已知 S 是一个小于 11 的循环小数，请计算与 S 相等的最简真分数是多少。 例如 0.3333⋯0.3333⋯ 等于 1331 ，0.1666⋯0.1666⋯ 等于 1661 。
输入描述 输入第一行包含两个整数 p 和 q，表示…
Miller-Rabin素数测试（被测数可以是小于2^63的正整数）
首先改算法原理是基于费马小定理： 假如p是素数，且gcd(a,p)1，那么a^(p-1)%p1
推论： 若p是素数且a是正整数，那么a^p%pa
定义：令a是一正整数，若n是合数且满足a^n%na,则n称为以a为基的伪素数 素数…
HUD—6287，口算训练，思维，素因子分解，lower_bound， upper_bound
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 512000/512000 K (Java/Others) Total Submission(s): 6517 Accepted Submission(s): 1423 Problem Description 小Q非常喜欢数学，但是他的口算能力非常弱。因此他找到了小T，给了小T一个长…
C# 求3个数的最小公倍数之数论革命
相关导读：
C# 求3个数的最小公倍数之代数革命
https://blog.csdn.net/number1killer/article/details/88570888
Java求三个数的最小公倍数算法改进（化境）
https://blog.csdn.net/number1killer/article/details/84143490
Java求三个数的最小公倍数算法优化
https://bl…
[bzoj1008][HNOI2008]越狱
Description
求n个数排成一行，每个数都在1~m范围内且相邻两个数至少有一组相同的方案数。 n<10^12,m<10^8
Solution
发现直接计算很麻烦。 正难则反，我们考虑用总数-不合法的方案数。 总数很显然是mn那么不合法的方案数就是 第一个位置可以…
第十三届蓝桥杯省赛C/C++,JAVA,Python研究生组题 质因数个数
4658. 质因数个数 - AcWing题库 给定正整数 n，请问有多少个质数是 n 的约数。 输入格式 输入的第一行包含一个整数 n。 输出格式 输出一个整数，表示 n 的质数约数个数。 数据范围 对于 30%30% 的评测用例，1≤n≤10000 对于 60%60% 的评测用例…
「MtOI2019」幽灵乐团
Description
求∏i1A∏j1B∏k1C([i,j](i,k))f(type)\prod_{i1}^{A}\prod_{j1}^{B}\prod_{k1}^{C}({[i,j]\over (i,k)})^{f(type)}i1∏Aj1∏Bk1∏C((i,k)[i,j])f(type) f(0)1,f(1)ijk,f(2)(i,j,k)f(0)1,f(1)ijk,f(2)(i,j,k)f(0)1,f(1)ijk,f(2)(i,j,k) 设T为数据组数 A,…
【蓝桥杯集训·每日一题】AcWing 3792. 质数问题
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴筛质数埃氏筛法线性筛法一、题目
1、原题链接 3792. 质数问题 2、题目描述 给定两个整数 n 和 k，请你判断在 [2,n] 的范围内是否存在不少于 k 个质数ÿ…
[校内模拟]抬头仰望梦的脚步
Description
一棵二叉搜索树，插入n次，第i次插入的节点权值为(abn)%m，问第n次插入的点的深度 T<5e4,n<1e16,a,b,m<1e8
Solution
定义val(n)表示第n个数的权值，suf(v)表示所有的(abn)%m中，大于v的最小的数&a…
蓝桥杯数论总结：最大公约数和最小公倍数（原理+性质证明+python板子）
目录 最大公约数
手写GCD
最小公倍数
推导LCM函数表达式
GCD基本性质
性质的证明
取模运算基本性质
证明 最大公约数
gcd是最大公约数的意思。Python的math库里有gcd函数。
在Python命令行运行gcd，可发现其可传入0、不会返回负数、可对多个数进行判断的性质…
Codeforces Round 932 (Div. 2)（A,B,C,D）
比赛链接
AB都是思维，更确切地说，A考了字符串字典序，很经典的贪心考点，B考了MEX运算。C出的还是比较好的，dp方法值得学习。D题是个不太好想的容斥，主要是变量有点多，容易搞混。 A. Entertainme…
PLONK电路如何构造，PLONK例子
文章目录个人总结如何理解电路Gate ConstraintsCopy constraints多项式承诺参考资料个人总结
PlonK相比起之前的zkSNARK协议来说，主要区别在于三点，
1-首先是在将电路解释为多项式的时候，SNARK协议一般采用R1CS到QAP的做法，最后…
【NOIP2016提高A组模拟9.15】Math
Description
求∑i1n(−1)∑mj1d(i∗j)其中d(i)表示i的因子个数。 n<10^7,m<10^14Solution
既然是-1的次幂，那么我们就来分析一下奇偶性吧。。。 这里有一个很（不）显然的性质，d(n)是奇数当且仅当n是一个完全平方数。 然…
【GDOI2017模拟8.14】佐助的难题
Description
给出n和m，求n!的范围中与m!互质的数的个数。答案对r取模。 n,m<1e7，r>n>m，且r为质数。
Solution
首先，如果gcd(a,b)1，那么gcd(ab,b)1. 所以，1~km与m互质的数的个数为k∗φ(m)答案…
分圆多项式 cyclotomic polynomial
翻译自维基百科
数学上将第nnn个分圆多项式写作Φn(X)\Phi_n(X)Φn(X)。
定义为：
对于任意正整数nnn，Φn(X)\Phi_n(X)Φn(X)是一个不可约的首一多项式，满足Φn(X)∣xn−1\Phi_n(X)|x^n-1Φn(X)∣xn−1，任意k<nk<nk…
HDU 1576 （A/B）扩展欧几里德定理
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64uHDU 1576Description 要求(A/B)%9973，但由于A很大，我们只给出n(nA%9973)(我们给定的A必能被B整除，且gcd(B,9973) 1)。Input 数据的第一行是一个T…
求一个数的因子数以及因子和
转自：杨美人！ (a/b) mod ma mod (bm)/b
//求因子个数
int count(int n){int s1;for(int i2;i*i<n;i){if(n%i0){int a0;while(n%i0){n/i;a;}ss*(a1);}}if(n>1) ss*2;return s;
}
//求因子和
int sum(int n){int s1;for(int i2;i*i<n;i){if(n…
![题245.数论-洛谷P1313 [NOIP2011 提高组] 计算系数](https://img-blog.csdnimg.cn/52de5f7fb47645ee9bc9dfb08debbe16.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQWRvbmd1YQ==,size_20,color_FFFFFF,t_70,g_se,x_16)
题245.数论-洛谷P1313 [NOIP2011 提高组] 计算系数
文章目录题245.数论-洛谷P1313 [NOIP2011 提高组] 计算系数一、题目二、题解题245.数论-洛谷P1313 [NOIP2011 提高组] 计算系数 一、题目 二、题解 首先推导公式我们可以知道我们要求的系数其实就是a的n次方乘以b的m次方再乘上m,k组合数。对于a的n次方和b的m次方，我…
题270.2022分队天梯赛训练-7-48 最大公约数 (20 分)
文章目录题270.2022分队天梯赛训练-7-48 最大公约数 (20 分)一、题目二、题解题270.2022分队天梯赛训练-7-48 最大公约数 (20 分) 一、题目 二、题解 记住一个公式：gcd(am-bm,an-bn)agcd(m,n)-bgcd(m,n) #include <bits/stdc.h>using namespace std;typedef u…
与反素数有关的3个题目
前置技能：
1.反素数，推荐博客：ACdreamers讲解反素数。定义：对于任何正整数 n ,其约数的个数记做 f(n) .例如 f(1) 1, f(6) 4 .如果某个正整数n满足：对于任意 i ( 0 < i < n ) ,都有 f( i ) < f( n ),则称 …
bzoj 2186: [Sdoi2008]沙拉公主的困惑
Description 大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为1到N的阶乘，但是，政府只发行编号与M!互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现…
公约数（acwing每日一题）
题目描述：
给定两个正整数 a 和 b。
你需要回答 q个询问。
每个询问给定两个整数 l,r，你需要找到最大的整数 x，满足：
x 是 a 和 b的公约数。l≤x≤r。
输入格式：
第一行包含两个整数 a,b。
第二行包含一个整数 …
Leetcode.2344 使数组可以被整除的最少删除次数
题目链接 Leetcode.2344 使数组可以被整除的最少删除次数 Rating ： 1641 题目描述
给你两个正整数数组 numsnumsnums 和 numsDividenumsDividenumsDivide 。你可以从 numsnumsnums 中删除任意数目的元素。
请你返回使 numsnumsnums 中 最小 元素可以整除 numsDivi…
转圈游戏（acwing）
题目描述：
n 个小伙伴（编号从 0 到 n−1）围坐一圈玩游戏。
按照顺时针方向给 n 个位置编号，从 0 到 n−1。
最初，第 0 号小伙伴在第 0 号位置，第 1 号小伙伴在第 1 号位置，…
刘汝佳の扩展欧几里得算法详解
引
直线上的点
求直线 a x b y c 0 axbyc0 axbyc0上有多少个整点 ( x , y ) (x,y) (x,y)满足 x ∈ [ x 1 , x 2 ] , y ∈ [ y 1 , y 2 ] x\in[x1,x2],y\in[y1,y2] x∈[x1,x2],y∈[y1,y2]
扩展欧几里得算法
在解决引中的问题之前，我们需要学习一下扩展欧几里得…
蓝桥杯刷题-12-公因数匹配-数论（分解质因数）不是很理解❓❓
蓝桥杯2023年第十四届省赛真题-公因数匹配
给定 n 个正整数 Ai，请找出两个数 i, j 使得 i < j 且 Ai 和 Aj 存在大于 1 的公因数。 如果存在多组 i, j，请输出 i 最小的那组。如果仍然存在多组 i, j，请输出 i 最小的所有方案中 j 最小的那…
[51nod1190]最小公倍数之和V2
Description
给出a,b，求∑iablcm(i,b)∑iablcm(i,b)a,b<1e9,数据组数<1e5,答案对1e97取模Solution
看到gcd想反演（然而这个是lcm） 这个反演不是正常套路 坑了我好久才跳出来 首先ansb∑d|b1d∑iabi[gcd(i,b)d]ansb∑d|b1d∑iabi[g…
poj 1006 中国剩余定理
根据单因子构件凑成法（能对于变化的余数都能快速求解）
思想：求出23， 28， 33三个互素（前提）的分别余数为一的情况， 就介绍式一的情况，其他两式同理可得。
式一ÿ…
【WinterCamp 2013】模积和
Description
求∑i1n∑j1,j≠im(nmodi)∗(mmodj)n,m<10^9，答案模19940417Solution
首先，看到有%，心里很不爽，把它变成n−⌊ni⌋∗i，对于i≠j的情况，后面减去就可以了。我们设n<m于是原式就变成了 …
【数学】【数论】【最大公约数】1819. 序列中不同最大公约数的数目
作者推荐
视频算法专题
本博文涉及知识点
数学 数论
LeetCode1819. 序列中不同最大公约数的数目
给你一个由正整数组成的数组 nums 。 数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。 例如，序列 [4,6,16] 的最大公约数是 2 。 数组的一个…
【数论】莫比乌斯反演巩固1
文章目录 前言 洛谷P3455洛谷P1829洛谷P4449 前言
这里需要对莫反有一些基础。 不会的可以点这里
洛谷P3455
题意： 给定 a , b , d a,b,d a,b,d 求 ∑ x 1 a ∑ y 1 b [ gcd ( x , y ) d ] \sum_{x1}^a\sum_{y1}^b[\gcd(x,y)d] ∑x1a∑y1b[gcd(x,y)d…
RSA解密-第十届Java研究生组E题
RSA解密-第十届Java研究生组E题 1、题目描述2、解题思路3、完整代码1、题目描述 本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。 RSA 是一种经典的加密算法。它的基本加密过程如下。 首先生成两个质数 p,q，令 n=p⋅q，设 d 与 (p−1)⋅(q−1) 互质…
Continued Fractions（数论，开方法）
2023-2024 ICPC, Swiss Subregional
C. Continued Fractions
题目链接 Continued Fractions
题意：
给定正整数 p p p，求使得 a b p \dfrac abp bap，且 a 1 b 1 , a 2 b 2 \dfrac{a1}{b1},\dfrac{a2}{b2} b1a1,b2a2 为整数的…
2017多校训练Contest3: 1008 RXD and math hdu6063
RXD is a good mathematician.One day he wants to calculate:∑i1nkμ2(i)⌊nki−−−√⌋output the answer module 1097.1≤n,k≤1018μ(n)1(n1)μ(n)(−1)k(np1p2…pk)μ(n)0(otherwise)p1,p2,p3…pkare different prime numbersInputThere are several test cases, please…
组合数学——求组合数
对于求组合数，要根据所给数据范围来选择合适的算法
求组合数 I
这道题中所给的数据范围适合用打表的方法直接暴力求解 先用4e6的复杂度预处理出所有的情况，再用1e4的复杂度完成询问即可
#include <bits/stdc.h>
using namespace std;
const int…
【动态规划】【滑动窗口】【C++算法】 629K 个逆序对数组
作者推荐
【矩阵快速幂】封装类及测试用例及样例
本文涉及知识点
动态规划 C算法：滑动窗口总结
LeetCode629: K 个逆序对数组
逆序对的定义如下：对于数组 nums 的第 i 个和第 j 个元素，如果满足 0 < i < j < nums.length 且 nu…
数论基础——循环节和矩阵快速幂的运用
首先我们来看一道基础题： 题目链接：HDU1005 Number Sequence 题目描述： Number Sequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 147421 Accepted Submission(s): …
数论-Description has only two Sentences HDU - 3307 （欧拉函数+欧拉定理）
欧拉定理表明，若n,a为正整数，且n,a互质，则: 费马小定理: a是不能被质数p整除的正整数，则有a^(p-1) ≡ 1 (mod p) 证明这个定理非常简单，由于p是质数，所以有φ p-1，代入欧拉定理即可证明。推论…
![P1463 [POI2001][HAOI2007]反素数 题解](https://img-blog.csdnimg.cn/20190824213958969.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXJwX2xlZ2VuZGdvZA==,size_16,color_FFFFFF,t_70)
P1463 [POI2001][HAOI2007]反素数 题解
P1463 [POI2001][HAOI2007]反素数 题解
题意分析 首先这是一个数论题 Solution\tt SolutionSolution 根据数据分析得出 29<前十个质数的乘积2^9<\text{前十个质数的乘积}29<前十个质数的乘积 由此判断出所有数中所含有的质数不会超过 101010 个 即 2,3,5,7,11,13,17,…
AcWing蓝桥杯AB组辅导课08、数论
文章目录前言一、数论例题例题1：AcWing 1246. 等差数列（最大公约数，第十届蓝桥杯省赛CB第7题）分析题解：最大公约数例题2：AcWing 1295. X的因子链（算数基本定理、欧拉筛选，多重集合排…
2023牛客寒假算法基础集训营2 -- E-Tokitsukaze and Function(数学 二分)
题目如下： TokitsukazeTokitsukazeTokitsukaze 有一个函数 f(x)⌊xn⌋x−1f(x)⌊\frac{x}{n}⌋x−1f(x)⌊nx⌋x−1 她想在区间 [L,R][L,R][L,R] 中找到一个最小的整数 ttt, 使函数 f(t)f(t)f(t) 的值最小。
输入描述:
第一行包含一个整数 TTT (1≤T≤2∗105)(1 …
扩展欧几里得算法的一种自顶向下实现
上一次发博客已然是将近四年前，疫情还没开始的时候。 在这段时间里我暂别了OI，但是兜兜转转还是回到了计算机这一我一直向往的领域。 去年这个时候也动笔尝试写过一篇博客，但是工程量似乎比我想象中的要大些，自然烂尾了。 但今天登…
C++ 【NOIP2011】计算系数——利用另类DP巧解
题目描述
给定一个多项式(ax by)^k，请求出多项式展开后x^n y^m项的系数。
输入
输入文件名为 factor.in。 共一行，包含 5 个整数，分别为a，b，k，n，m，每两个整数之间用一个空格隔开…
【蓝桥杯集训20】质数（3 / 3）
目录
试除法判断质数
分解质因数
筛质数模板
1、朴素筛
2、埃氏筛
3、线性筛
3792. 质数问题 - 筛质数 试除法判断质数
import java.util.*;class Main
{public static boolean isprime(int x){if(x<2) return false;for(int i2;i<x/i;i)if(x%i0) return false;r…
Large-Precision Sign using PBS
参考文献：
[CLOT21] Chillotti I, Ligier D, Orfila J B, et al. Improved programmable bootstrapping with larger precision and efficient arithmetic circuits for TFHE[C]//Advances in Cryptology–ASIACRYPT 2021: 27th International Conference on the T…
等差数列（蓝桥杯，acwing每日一题）
题目描述：
数学老师给小明出了一道等差数列求和的题目。
但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？
输入格式：
输入的第一…
Lucas定理和拓展Lucas定理
用途
对于一个组合数求值的问题，一般运用阶乘来求，但有时候阶乘太大，就会超时。
而 LucasLucasLucas 定理和拓展 LucasLucasLucas 定理就是用来解决在模意义下求值的问题。（但有个前提，就是你的模数必须比较小&#…
C++ [NOIP2002]选数题解——简单数论与DFS的运用
问题 F(1413): [NOIP2002]选数
时间限制: 1 Sec 内存限制: 64 MB
题目描述
已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n4，k&…
求3个数的最小公倍数算法之数论全覆盖（C# ）
求3个数的最小公倍数之便捷算法（C# )
https://blog.csdn.net/number1killer/article/details/104681168
求3个数的最大公约数之算法研究集成（C#）
https://blog.csdn.net/number1killer/article/details/104637728
求3个数的最小公倍数之算法简化（C# ）
https://blog.c…
求3个数的最小公倍数算法之数论再细化
求3个数的最小公倍数之便捷算法（C# )
https://blog.csdn.net/number1killer/article/details/104681168
求3个数的最大公约数之算法研究集成（C#）
https://blog.csdn.net/number1killer/article/details/104637728
求3个数的最小公倍数之算法简化（C# ）
https://blog.c…
C++二分查找算法的应用：长度递增组的最大数目
本文涉及的基础知识点
二分查找
题目
给你一个下标从 0 开始、长度为 n 的数组 usageLimits 。 你的任务是使用从 0 到 n - 1 的数字创建若干组，并确保每个数字 i 在 所有组 中使用的次数总共不超过 usageLimits[i] 次。此外，还必须满足以下条件&…
![bzoj 2190: [SDOI2008]仪仗队](http://www.lydsy.com/JudgeOnline/images/2190.jpg)
bzoj 2190: [SDOI2008]仪仗队
Description 作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 现在&…
Codeforces Round 903 (Div. 3)ABCDE
Codeforces Round 903 (Div. 3)ABCDE 目录 A. Dont Try to Count题目大意思路核心代码 B. Three Threadlets题目大意思路核心代码 C. Perfect Square题目大意思路核心代码 D. Divide and Equalize题目大意思路核心代码 E. Block Sequence题目大意思路核心代码 A. Don’t Try t…
求自然数幂和的各种方法（还有坑）
求∑i1nikmodp高斯消元
一个定理，k次方和一定可以由0~k-1次方和表示出来，设方程组解出来就好了。 O(k3)倍增
我们设f(n,k)∑i1nik怎么算呢？ 我们采用分治思想。 如果n是奇数那么 f(n,k)f(n−1,k)nk否则，我们可以先求出n/2的f&a…
群环域，理想商环，原根复习
包含了抽象代数里面的一些概念，最近看文章的时候一直反映不过来，理想是个啥来着，环和域的区别是啥来着。所以统筹整理一下。 文章目录集合/(Set)：半群/(Monoid)：群(G,⋅)(G,\cdot)(G,⋅)/(Group)：交换群/(C…
【学习笔记】莫比乌斯反演
退役OIer回来受虐啦
一些定义 μ ( x ) { 1 x > 1 ( − 1 ) n x ∏ i 1 n P i 0 o t h e r w i s e \mu(x) \begin{cases} 1 & x > 1 \\ (-1)^n & x \prod _ {i1} ^ {n} P_{i}\\ 0 & otherwise \end{cases} μ(x)⎩ ⎨ ⎧1(−1)n0x>1x∏i1nPi…
HDU-1568Fib前四位
题意：输出Fibonacci数组的前四位,n<100000000; 思路：
首先:看到这个题的数据范围,0(n)的时间复杂度是不行的。 然后想下数组可不可以用来储存呢?n<100000000,数太大了,就算表示 ,也会超时。 再想是不是有循环节,但是前四位的是跟后面几位有关系的…
费马小定理，876. 快速幂求逆元
876. 快速幂求逆元 - AcWing题库
给定 n 组 ai,pi，其中 pi 是质数，求 ai 模 pi 的乘法逆元，若逆元不存在则输出 impossible。
注意：请返回在 0∼p−1 之间的逆元。
乘法逆元的定义 若整数 b，m 互质，并且…
Every one will meet some difficult
###Description 求方程∑i1mxi<s\sum_{i1}^{m}xi<s∑i1mxi<s且对于i1~n，xi<txi<txi<t的正整数解数。 n,m<1e9,nt<s<1e18,m-n<1e3
###Beat the Challeng ####Part 1 答案等于∑i0n(−1)iCniCs−tim\sum_{i0}^{n}(-1)^iC_n^iC_{s-ti…
分巧克力（蓝桥杯，二分，acwing）
题目描述：
儿童节那天有 K 位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N 块巧克力，其中第 i 块是 HiWi的方格组成的长方形。
为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。
切出…
Codeforces Round 846 (Div. 2) E. Josuke and Complete Graph 详解 数论分块
题目大意 题意来源 解题思路
首先我们假设存在 x x x满足 a , b ∈ [ l , r ] , g c d ( a , b ) x a,b\in[l,r],gcd(a,b)x a,b∈[l,r],gcd(a,b)x那么肯定 g c d ( ⌊ a / x ⌋ , ⌊ b / x ⌋ ) 1 就是互质 gcd(\lfloor a/x \rfloor, \lfloor b/x \rfloor)1就是互质 gcd(⌊a…
牛客周赛 Round 35（A,B,C,D,E,F,G）
这场简单，甚至赛时90分钟不到就AK了。比赛链接，队友题解友链
刚入住学校监狱，很不适应，最近难受的要死，加上最近几场CF打的都不顺利，san值要爆掉了，只能慢慢补题了。
这场C是个滑动窗口&#…
【GDOI2017模拟9.24】周末晚会
Description
求n个点的圆排列，每个点是1或0，并且连续的0不超过k个的方案数。 循环同构算一种。多组数据。 T<50,n,k<2000
Solution
首先，先不考虑环的情况，我们来处理一下连续的k个。 一个很显然的想法是，…
SDUT 2605 山东省第四届ACM省赛 A^X mod P （数论打表）
传送门：SDUT 2605题目大意：
给你 7 个整数： n, A, K, a, b, m, P，以及一个 f(x) 的表达式：f(x) K, x 1f(x) (a*f(x-1) b)%m , x > 1
让你计算：( A^(f(1)) A^(f(2)) A^(f(3)) ...... A^(f(n)) ) …
【数学】完全剩余系与费马小定理
完全剩余系
我们定义 a i ( 1 ≤ i ≤ n ) a_i(1\le i\le n) ai(1≤i≤n) 为模 m m m 的完全剩余系当且仅当对于 1 ≤ i , j ≤ n 1\le i,j\le n 1≤i,j≤n 且 i ≠ j i\ne j ij，满足 a i ≢ a j ( m o d m ) a_i\not\equiv a_j\pmod m ai≡aj(mo…
C++浅析斜率优化的推导过程
斜率优化推导
第一次看可能会不懂，但多看几遍就会懂了，废话不多说，直接开始推导吧 对于一个动态转移方程 dp[ i ] dp[ j ] M ( sum[ i ] - sum[ j ] )^2
假设两个决策点 k , j ，且 j 比 k 更优（这里就是 dp[ j …
[51nod1379]索函数
Description
求fib(0)|fib(1)|fib(2)|...|fib(n)mod1e97n<10^10Solution
因为一直是或，所以我们的答案二进制位的每一位都是1. 那么答案就是fib(n)的位数k,2^(k1)-1. 那么我们就是要快速求出fib(n)的位数。 当n较小的时候，我们就可以直接求出来了…
高斯消元法解01异或方程组（附poj 1222题解）
const int maxn50;
//有equ个方程，var个变元。增广矩阵行数为equ，列数为var1
int equ,var;
int a[maxn][maxn]; //增广矩阵
int x[maxn]; //解集
int free_x[maxn];
int free_num;
void init(){memset(a,0,sizeof(a));memset(x,0,sizeof(x));equ30,var3…
C++解题报告：迷路[SCOI2009]——巧妙运用加速矩阵快速求解
引言
好题一道，恶心到爆。。。 迷路 题目描述 windy在有向图中迷路了。 该有向图有 N 个节点，windy从节点 0 出发，他必须恰好在 T 时刻到达节点 N-1。 现在给出该有向图，你能告诉windy总共有多少种不同的路径吗？ 注意…
GDSOI 2016 T1 互补约数
Description
求∑i1n∑d|igcd(d,id)n<10^11Solution
首先，我们发现gcd中的两个东西是所有乘积不超过n的数对，即 Ans∑i∑j,i∗j<ngcd(i,j)然后Ans∑i1n∑j1⌊ni⌋gcd(i,j)咦？ 长得那么像莫比乌斯的经典形式。只不过j的上界是会变化的…
【GDOI2018模拟8.11】质数
Description
求∑i1n2f(i)f(i)表示i的不同的质因子个数 n<10^12Solution
我们设g(i)2^f(i),显然g是积性函数 那么我们可以尝试杜教筛g 把g卷上一个mu，设g*muh 显然h也是积性函数 分析一下h(p^k)，我们可以发现h(p^k)[k1] 特别的h[1]1 那么归纳…
完全平方数（蓝桥杯，acwing，数论）
题目描述：
一个整数 a 是一个完全平方数，是指它是某一个整数的平方，即存在一个整数 b，使得 ab^2。
给定一个正整数 n，请找到最小的正整数 x，使得它们的乘积是一个完全平方数。
输入格式：
输…
【矩阵】【方向】【素数】3044 出现频率最高的素数
作者推荐
动态规划的时间复杂度优化
本文涉及知识点
素数 矩阵 方向
LeetCode 3044 出现频率最高的素数
给你一个大小为 m x n 、下标从 0 开始的二维矩阵 mat 。在每个单元格，你可以按以下方式生成数字： 最多有 8 条路径可以选择：东&am…
Leetcode.914 卡牌分组
题目链接 Leetcode.914 卡牌分组 Rating ： 1371 题目描述
给定一副牌，每张牌上都写着一个整数。
此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：
每组都有 X 张牌。组内所有的牌上都写…
质因数个数(acwing,蓝桥杯）
题目描述：
给定正整数 n，请问有多少个质数是 n 的约数。
输入格式：
输入的第一行包含一个整数 n。
输出格式：
输出一个整数，表示 n 的质数约数个数。
数据范围：
对于 30% 的评测用例，1≤…
牛客周赛 Round 38（A,B,C,D,E,F,G）
比赛链接
官方讲解（不分P不分段直接两小时怼上来是坏文明 ）
这场的题很棒，思维有难度，考察的知识点广泛，有深度，很透彻。感觉学到了很多。建议补题。 A 小红的正整数自增
思路：
签到。
可以…
信息竞赛笔记(2)––快速幂
目录
快速幂
定义
分析
代码
递归实现
非递归实现(通用方法) 模意义下取幂 快速幂
定义 快速幂,二进制取幂(Binary Exponentiation,也称平方法),是一个在的时间内计算的小技巧，而暴力的计算需要的时间。 这个技巧也常常用在非计算的场景，因为它可…
[AGC031F]Walk on Graph
Description
有一张n个点m条边的无向连通图G，每条边有长度ci，有一个人在上面走 有q组询问，每组询问给出si,ti,ri，表示问你是否存在一条从si出发到ti结束长度为ri%Mod的路径 注意这里的路径长度是∑ci*2^i n,m,q<50000,Mod<…
【数位dp】【数论】【动态规划】2999. 统计强大整数的数目
作者推荐
视频算法专题
作者推荐
动态规划的时间复杂度优化
本文涉及知识点
数位 数论
LeetCode2999. 统计强大整数的数目
给你三个整数 start ，finish 和 limit 。同时给你一个下标从 0 开始的字符串 s ，表示一个 正 整数。 如果一个 正 整数 x …
C++解题报告：Tokitsukaze, CSL and Stone Game[ COCI ] —— 博弈论
题目描述 Irressey与yurzhang在玩一个取石子的游戏 一开始，他们面前有nn堆石子，第ii堆石子有a_iai颗石头，他们轮流取石子（Irressey先取）。每一次，取石子的人会选中一个非空的石子堆并取走其中的一颗石子。…
![[蓝桥双周赛]铺地砖](https://img-blog.csdnimg.cn/f09d2d6c6a824cc39b30b8b4cfbab1b9.png)
[蓝桥双周赛]铺地砖
题目描述
小蓝家要装修了，小蓝爸爸买来了很多块（你可以理解为数量无限)23规格的地砖，小蓝家的地板是n m规格的，小蓝想问你，能否用这些23的地砖铺满地板。
铺满地板:对于地板的每个区域，都有且只有一块地…
【算法】数论——筛质数（线性筛法）
题目
给定一个正整数 n，请你求出 1∼n 中质数的个数。
输入格式
共一行，包含整数 n。
输出格式
共一行，包含一个整数，表示 1∼n 中质数的个数。
数据范围
1 ≤ n ≤ 10^6
思路
朴素筛法做法:把2~(n-1)中的所有的数的倍数…
【蓝桥杯集训·每日一题】AcWing 4309. 消灭老鼠
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴最大公约数一、题目
1、原题链接 4309. 消灭老鼠 2、题目描述 约翰的农场可以看作一个二维平面。 农场中有 n 个老鼠，在毁坏着农田。 第 i 个老鼠的位置坐标为…
【五校联考2day2】WYF的盒子
Description
求∑imnikmodp90% n,m,p<10^12,k<2000 另外10% n-m<5000,n,m,p,k<10^12Solution
采用自然数幂和 注意，这种东西的模数比较大，两个乘起来会爆longlong。 于是可以用乘法取模黑科技 （懒癌发作ing~）
C…
The 2023 ICPC Asia Regionals Online Contest (1) E. Magical Pair（数论 欧拉函数）
题目
T(T<10)组样例，每次给出一个n(2<n<1e18)，
询问多少对，满足
答案对998244353取模，保证n-1不是998244353倍数
思路来源
OEIS、SSerxhs、官方题解
2023 ICPC 网络赛 第一场简要题解 - 知乎
题解
官方题解还没有…
1312. 序列统计
1312. 序列统计 - AcWing题库 L~R范围可以等同于0~R-L范围 相当于在R-L1个数中选出k个数 令
则变为
相当于在R-Lk个数中选出k个数 需要计算 #include<bits/stdc.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl \nusing namespace std;t…
