文章目录[蓝桥杯2021省AB2]完全平方数题目描述输入格式输出格式样例#1样例输入#1样例输出#1样例#2样例输入#2样例输出#2提示思路：理论补充：完全平方数的一个性质：完全平方数的质因子的指数一定为偶数最终思路：小插曲：全部代码[蓝桥杯2021省AB2]完全平方数题目描述一个整数aaa是一个完全平方数，是指它是某一个整数的平方，即存在一个整数bbb，使得a=b2a=b^{2}a=b2。给定一个正整数nnn，请找到最小的正整数xxx，使得它们的乘积是一个完全平方数。输入格式输入一行包含一个正整数nnn。输出格式输出找到的最小的正整数xxx。样例#1样例输入#112样例输出#13样例#2样例
文章目录[蓝桥杯2021省AB2]完全平方数题目描述输入格式输出格式样例#1样例输入#1样例输出#1样例#2样例输入#2样例输出#2提示思路：理论补充：完全平方数的一个性质：完全平方数的质因子的指数一定为偶数最终思路：小插曲：全部代码[蓝桥杯2021省AB2]完全平方数题目描述一个整数aaa是一个完全平方数，是指它是某一个整数的平方，即存在一个整数bbb，使得a=b2a=b^{2}a=b2。给定一个正整数nnn，请找到最小的正整数xxx，使得它们的乘积是一个完全平方数。输入格式输入一行包含一个正整数nnn。输出格式输出找到的最小的正整数xxx。样例#1样例输入#112样例输出#13样例#2样例
平方剩余、二次互反律一、平方剩余定义：设p为奇素数且\(\mathsf{a\neq0\mod\p}\)，如果a在模p下是另一个数的平方，即\(\mathsf{a\equivb^{2}\mod\p}\)，则称a为模p下的平方剩余，否则称a为平方非剩余。而二次同余式\(\mathsf{x^{2}\equiva\mod\p}\)可能有0—2个解例子：\(\mathsf{p=5}\)时，因为\(\mathsf{1^{2}\equiv1\mod\5\qquad2^{2}\equiv4\mod\5\qquad3^{2}\equiv4\mod\5\qquad4^{2}\equiv1\mod\5}\)则1，4
平方剩余、二次互反律一、平方剩余定义：设p为奇素数且\(\mathsf{a\neq0\mod\p}\)，如果a在模p下是另一个数的平方，即\(\mathsf{a\equivb^{2}\mod\p}\)，则称a为模p下的平方剩余，否则称a为平方非剩余。而二次同余式\(\mathsf{x^{2}\equiva\mod\p}\)可能有0—2个解例子：\(\mathsf{p=5}\)时，因为\(\mathsf{1^{2}\equiv1\mod\5\qquad2^{2}\equiv4\mod\5\qquad3^{2}\equiv4\mod\5\qquad4^{2}\equiv1\mod\5}\)则1，4
在做数论题时，往往需要进行和式变换，然后变换成我们可以处理的和式，再针对和式做筛法、整除分块等操作。本文将介绍一些常见的和式变换技术。以下出现的概念大部分为个人总结，未必是学术界/竞赛界的统一说法，有不严谨的地方请谅解。?作者：Eriktse?简介：19岁，211计算机在读，现役ACM银牌选手?力争以通俗易懂的方式讲解算法！❤️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）??原文链接（阅读原文获得更好阅读体验）：https://www.eriktse.com/algorithm/1101.html和式的基本形式和式一般有两种：区间枚举型和整除枚举型。区间枚举型我们的
在做数论题时，往往需要进行和式变换，然后变换成我们可以处理的和式，再针对和式做筛法、整除分块等操作。本文将介绍一些常见的和式变换技术。以下出现的概念大部分为个人总结，未必是学术界/竞赛界的统一说法，有不严谨的地方请谅解。?作者：Eriktse?简介：19岁，211计算机在读，现役ACM银牌选手?力争以通俗易懂的方式讲解算法！❤️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）??原文链接（阅读原文获得更好阅读体验）：https://www.eriktse.com/algorithm/1101.html和式的基本形式和式一般有两种：区间枚举型和整除枚举型。区间枚举型我们的
初等数论学习笔记I：同余相关。初等数论学习笔记II：分解质因数。1.数论函数本篇笔记所有内容均与数论函数相关。因此充分了解各种数论函数的名称，定义，符号和性质是必要的。1.1相关定义数论函数：定义域为正整数的函数称为数论函数。因其在所有正整数处均有定义，故可视作数列。OI中常见的数论函数的陪域（即可能的取值范围）为整数。加性函数：若对于任意\(a,b\in\mathbb{N}_+\)且\(a\perpb\)均有\(f(ab)=f(a)+f(b)\)，则称\(f\)为加性函数。注意区分代数中的加性函数。积性函数：若对于任意\(a,b\in\mathbb{N}_+\)且\(a\perpb\)均有\
初等数论学习笔记I：同余相关。初等数论学习笔记II：分解质因数。1.数论函数本篇笔记所有内容均与数论函数相关。因此充分了解各种数论函数的名称，定义，符号和性质是必要的。1.1相关定义数论函数：定义域为正整数的函数称为数论函数。因其在所有正整数处均有定义，故可视作数列。OI中常见的数论函数的陪域（即可能的取值范围）为整数。加性函数：若对于任意\(a,b\in\mathbb{N}_+\)且\(a\perpb\)均有\(f(ab)=f(a)+f(b)\)，则称\(f\)为加性函数。注意区分代数中的加性函数。积性函数：若对于任意\(a,b\in\mathbb{N}_+\)且\(a\perpb\)均有\
数论合集\(Part\)\(1\):裴蜀定理定理：对于任意整数\(a,b\)，记\(\gcd(a,b)=d\)，则对于所有整数\(x,y\)，都有\(d|ax+by\)，特别的，一定存在整数\(x,y\)使得\(ax+by=d\)。证明：因为\(d=gcd(a,b)\)，所以有\(a\equivb\equiv0\pmodd\)，所以\(ax+by\equiv0\timesx+0\timesy\equiv0\pmodd\)，所以\(d|ax+by\)。记所有\(ax+by\)的集合为\(S\)，设\(w=ax_1+by_1\)是\(S\)中的最小正值，则有\(w\ged\)；对于所有\(u=ax
数论合集\(Part\)\(1\):裴蜀定理定理：对于任意整数\(a,b\)，记\(\gcd(a,b)=d\)，则对于所有整数\(x,y\)，都有\(d|ax+by\)，特别的，一定存在整数\(x,y\)使得\(ax+by=d\)。证明：因为\(d=gcd(a,b)\)，所以有\(a\equivb\equiv0\pmodd\)，所以\(ax+by\equiv0\timesx+0\timesy\equiv0\pmodd\)，所以\(d|ax+by\)。记所有\(ax+by\)的集合为\(S\)，设\(w=ax_1+by_1\)是\(S\)中的最小正值，则有\(w\ged\)；对于所有\(u=ax
