- 博客(20)
- 收藏
- 关注
RSS订阅原创 数论函数、积性函数、和函数
一、数论函数定义：数论函数指一类函数的称谓，这类函数的共同点是：定义域是正整数N*，值域是一个数集。加法：逐项相加即可数乘：用一个常数 x 乘f ( n ) = x ∗ f ( n )例如：，表示正整数n的正因子之和。，表示正整数n的正因子个数。二、积性函数（一）、积性函数定义：如果一个数论函数 f（）满足：当gcd(n,m)==1时，f ( n ∗ m ) = f ( n ) ∗ f ( m ) ，则 f（）为积性函数。（二）、完全积性函数定义：当gcd(n,m) ≠ 1 时
2021-11-03 07:27:56
2267
原创 uva557或P2719 搞笑世界杯的三种解法
传送门题意翻译设一共有nn个汉堡（nn为偶数且n<=100000n<=100000），其中有n/2n/2个火腿汉堡，n/2n/2个芝士汉堡。nn个小朋友坐成一排，依次等概率抽选汉堡。有意思的是，抽完倒数第三个小朋友时，厨师发现抽不下去了，因为正好剩下了两个相同的汉堡。厨师觉得很有趣，想问你出现这种情况的概率。输入格式 第一行一个整数tt，表示测试组数。对于每组测试，输入一个nn，意义如上。输出格式 输出tt行，每行为对应测试的答案。输入输出样例输入 #1复制
2021-03-07 11:22:30
329
原创 离散化
一、概述数据离散化是一个非常重要的思想。为什么要离散化?当以权值为下标的时候，有时候值太大，存不下。 所以把要离散化的每一个数组里面的数映射到另一个值小一点的数组里面去。打个比方，某个题目告诉你有10^4个数，每个数大小不超过10^10，要你对这些数进行操作，那么肯定不能直接开10^10大小的数组，但是10^4的范围就完全没问题。我们来看一下定义：离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。（by百度百科）通俗的说，离散化是在不改变数据相对大小的条件下，对
2021-02-05 16:38:22
260
2
原创 P2882 [USACO07MAR]、POJ 3276 Face The Right Way（翻转问题 贪心+枚举+差分）
题意：N头牛排成一列1<=N<=5000。每头牛或者向前或者向后。为了让所有牛都面向前方，农夫每次可以将K头连续的牛转向1<=K<=N，求操作的最少次数M和对应的最小K。本题的模型是开关问题（或者叫翻转问题）。拿到题目，你肯定会思考两个问题，1、从哪里开始翻转，2、翻转多大的区间呢？发现一句话很重要Each time the machine is used, it reverses the facing direction of a contiguous group of K
2021-01-29 22:05:26
188
原创 莫比乌斯函数、莫比乌斯反演
莫比乌斯函数在学习这个函数之前，最好先了解欧拉函数莫比乌斯函数：数论函数，由德国数学家和天文学家莫比乌斯(Möbius ,1790–1868)提出。梅滕斯(Mertens)首先使用μ(n)作为莫比乌斯函数的记号。而据说，高斯(Gauss)比莫比乌斯早三十年就曾考虑过这个函数。莫比乌斯函数在数论中有着广泛应用。莫比乌斯函数完整定义的通俗表达：1）莫比乌斯函数μ(n)的定义域是N2）μ(1)=13）当n存在平方因子时，μ(n)=04）当n是素数或奇数个不同素数之积时，μ(n)= -15）当n
2020-11-18 10:18:25
7668
3
原创 图的连通性问题及Tarjan算法
推荐观看视频教程一、图的连通性1. 无向图的连通性在无向图G＝（V，E）中：①连通：若节点u和v能够互相到达，则称u,v是连通的；②连通图：若图中任何节点之间都是可互相到达的，则称G是连通图，否则称G是非连通图；这是一个连通图这不是一个连通图，③连通分量（连通分支）：我们可以看出上面右图有两个部分连通的图，叫做连通分量（或连通分支）④无向图的连通性判定：并查集、DF...
2020-02-04 20:21:11
1982
原创 欧几里得、扩展欧几里德及其应用（解不定方程、求逆元）www
一、欧几里得算法（中国叫辗转相除法）：gcd(a,b)=gcd(b,a%b)证明：设d是a、b的公因数（或公因子）则有d|a、d|b（根据整除定义）存在q1、q2使得a=q1*d、b=q2*d又因为对于整数a、b可写成b=aq+r（q是某一整数，r=a%b）所以q2*d=q1*d*q+r即r=q2*d-q1*d*q=(q2-q1*q)*d即d|r，也就是d|(a%b)得到结论一：a、...
2018-10-16 20:48:25
3965
1
原创 整除及其性质
整除的定义：若整数a除以非零整数b，商为整数，且余数为零， 我们就说a能被b整除（或说b能整除a），即b∣a,读作“b整除a”或“a能被b整除”。a叫做b的倍数，b叫做a的约数（或因数）。整除的基本性质及证明：①若a|b，a|c，则a|(b±c)。证明：因为a|b和a|c，所以∃q1,q2∈Z，使得b=q1*a c=q2*a，可推出b±c=q1*a±q2*a=(q1±q2)*a。...
2018-08-31 20:52:06
12523
1
转载 二分的应用
1. 计算 anan （数的幂）2. 计算 AnAn （矩阵的幂）由于矩阵乘法具有结合律，因此 A4=A∗A∗A∗A=(A∗A)∗(A∗A)=A2∗A2A4=A∗A∗A∗A=(A∗A)∗(A∗A)=A2∗A2我们可以得到这样的结论：当n为偶数时，An=An/2∗An/2An=An/2∗An/2 当n为奇数时，An=An/2∗An/2∗AAn=An/2∗An/2∗A （其中n/2取...
2018-07-23 11:44:38
470
转载 经常使用的构造散列函数的方法
散列表,它是基于高速存取的角度设计的，也是一种典型的“空间换时间”的做法。顾名思义，该数据结构能够理解为一个线性表，可是当中的元素不是紧密排列的，而是可能存在空隙。散列表（Hash table，也叫哈希表），是依据关键码值(Key value)而直接进行訪问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来訪问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。...
2018-07-22 17:15:49
565
原创 哈希算法和哈希表
转载自：http://baijiahao.baidu.com/s?id=1580022096840800840&wfr=spider&for=pc（“hash“”这个英文通常翻译成“哈希”，也有的书翻译成“散列”）在编程中常常要面临查找问题。哈希算法主要是利用哈希表（一种数据结构）进行高效地查找。最简单的解释脑补下，你是一个创（不）新（善）能（长）力（收）强（拾）的...
2018-07-22 16:19:27
322
转载 判断一个数是否为质数/素数——从普通判断算法到高效判断算法思路
转载https://blog.csdn.net/huang_miao_xin/article/details/51331710
2018-07-18 11:57:27
6281
转载 NOIP 2017 小凯的疑惑
引用博主：Hany01的文章 NOIP 2017 小凯的疑惑 （数学）博文地址：https://blog.csdn.net/hhaannyyii/article/details/78618358分析：（野路子：因为>=a*b的数都能由a和b组成，这个可以证明（此处省略）。那么就考虑小于a*b的数。简单想法就是找几对小的a和b，把最大不能组成的数推出，再尝试写出公式。（考试时学...
2018-07-18 10:39:21
941
转载 倍增算法思想（二分新姿势--倍增法）
建议先看看这篇博文：https://blog.csdn.net/JarjingX/article/details/8180560【白话系列】倍增算法 博主：JarjingX以下转自：https://blog.csdn.net/wybooooooooo/article/details/80778807博主：wybooooooooo的博客倍增思想举例A、B两点之间相隔若干单位为1的距离...
2018-07-17 17:32:20
12287
1
原创 分块学习小结
明天要开始讲二分、分块、倍增、差分等，今天先补一补！基础知识引用别人的一段话：一直觉得分块是一个很高端的东西…一直没敢碰，现在才知道分块就是一种稍微优美一些的暴力，所以没有学过分块的同学不要害怕啦…分块，就是将一段信息（数据结构，序列）分成几块处理，当然最基础的是序列上的分块，再高层点的就是树上的分块，分块套分块，分块套数据结构以及数据结构套分块。 顾名思义就是把要处理的东西进行分...
2018-07-17 16:53:17
370
原创 由取石子游戏想到的博弈论
先将本文的参考列表如下，以示对大咖的尊敬：作者：ojshilu 《两人取石子游戏 组合数学-博弈问题》作者：提比-我有特殊的AC技巧 《取石子游戏【各类取石子总结】》（该文也系转载） 有一种很有意思的游戏，就是有物体若干堆，可以是火柴棍或是围棋子等等均可。两个人轮流从堆中取物体若干，规定最后取光物体者取胜。这是我国民间很古老的一个游戏，别看这游戏极其简单，却蕴含着深刻的数学原理。下面...
2018-04-10 10:52:19
295
原创 输入一个整数矩阵，计算位于矩阵边缘的元素之和。所谓矩阵边缘的元素，就是第一行和最后一行的元素以及第一列和最后一列的元素。
输入第一行为整数k，表示有k组数据。每组数据有多行组成，表示一个矩阵：第一行分别为矩阵的行数m和列数n（m 接下来输入的m行数据中，每行包含n个整数，整数之间以空格作为间隔。输出输出对应矩阵的边缘元素和，一个一行。#include #include using namespace std;int main(){int m,n;
2018-01-31 07:21:52
12360
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人