Harris-H

数论

BFS(5) CF题解(3) DFS(20) DP(20) LCA(2) Leetcode(1) Nowcoder题解(4) ST(1) Tarjan(1) 二分(4) 二分法(1) 二叉树题目(4) 位运算(2) 前缀和(4) 博弈论(3) 图论(1) 字符串(5) 学习笔记(1) 并查集(2) 快速幂(1) 思维(7) 排序(1) 数状数组(3) 暴力(5) 最短路(5) 未归档(5) 标记处理(1) 栈(1) 概率论(1) 模拟(2) 浮点数(1) 生成树(4) 算法(5) 素数筛(3) 线段树(6) 组合数学(8) 蓝桥杯(1) 计算几何(1) 贪心(26) 递推(3) 题解(3) 高精度(2)

/ 注册

全部文章 / 数论（共20篇）

莫比乌斯反演定理的证明。

莫比乌斯反演定理的证明。初学给自己做个笔记，怕以后忘了。前置知识：莫比乌斯函数的两个性质：（这里证明用不到) 定理：若有定义在上的函数满足关系：，则有：证明：我们只需证上述等式右边等于左边即可。 = （定义) (1) = (分配律) (2) = (的地位是可交...

2020-05-28

1 1101

求前n个数因数和的三种方法。

求前个数因数和的三种方法。纯暴力，对每个数，遍历时间复杂度: #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<string...

2020-05-28

1 609

G - Eva's Balance (3进制&数论）

G - Eva's Balance (3进制&数论）题意：给个的幂次方数：和一个数，要求用这个数中若干个使左右两个秤盘数之和相等.（开始被放在左盘）思路：因为都是的幂次方,题目等价于构造两个的幂次方之和相减等于,所以考虑进制下来表示. 所以被转化为的数字串。当该位为时,显然可以不会用到或...

数论

2020-05-11

0 652

莫比乌斯函数

莫比乌斯函数 μ(n) ——默比乌斯函数，是关于非平方数的质因子数目，若n=1,μ(n) =1，若n存在有大于1的平方数因数（如4(2平方)，9（3的平方)，16（4的平方）……），则μ(n) =0，否则μ(n) 的结果取决于n根据算数基本定理分解的质因数个数的奇偶性来判断。比如n=3，...

2020-05-01

0 1082

Nowcoder practice 60 D.斩杀线计算大师(扩展欧几里得）

Nowcoder practice 60 D.斩杀线计算大师(扩展欧几里得）思路： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; #define mst...

2020-05-01

0 649

Codeforces Round #630 (Div. 2) B. Composite Coloring （数论）

Codeforces Round #630 (Div. 2) B. Composite Coloring （数论）题目传送门题意：给n个合数（存在两大于1相乘等于ai的因数）将最大公因数大于1的数分为一组，求每个数在哪个组（m<=11) 思路：ai<=1000，由数论知识可知任...

2020-05-01

0 665

Codeforces Round #630 (Div. 2) E. Height All the Same （快速幂&思维)

Codeforces Round #630 (Div. 2) E. Height All the Same （快速幂&思维) 题目传送门思路：分奇偶性讨论。 -------1.若N * M为奇数肯定可以，这N * M肯定是由偶数个+奇数个组成，不管是偶数个偶数还是偶数个奇数，偶数的一...

2020-05-01

0 902

AtCoder Grand Contest 043 B - 123 Triangle （组合数学&奇偶性）

AtCoder Grand Contest 043 B - 123 Triangle （组合数学&奇偶性）题目传送门题意：给长度为n由（1，2，3)组成序列求按相邻绝对差值运算后结果是多少。分析： ------ step1.由于是绝对差值，所以（1，2，3）等价于（0，1，2）运...

2020-05-01

0 607

P1017 进制转换（负进制&数论）

P1017 进制转换（负进制&数论）题目传送门题意：给一个整数和基数，要求转化以该基数的该进制。思路：题目主要难度为：余数可能是负数，因为转化为该进制表示时是用余数的倒序，由于除数(为负数)的绝对值比余数的绝对值大，所以用余数减去一个除数，商再加上一个除数即可以保证余数为正，且结...

2020-05-01

0 486

Codeforces Round #631 (Div. 2) D. Dreamoon Likes Sequences （位运算&组合数学）

Codeforces Round #631 (Div. 2) D. Dreamoon Likes Sequences （位运算&组合数学）题目传送门题意：给定d,mod,求所有满足ai在[1,d]且异或运算后bi<bi+1的所有数组A的个数。思路： AC代码 #in...

2020-05-01

0 668