已注销

数论

ACM模版篇(139) C++(4) CONTESTS(31) dfs && bfs(59) GitHub(1) Linux(4) OpenGL(2) PHP(5) Python(7) QT(3) Script(4) STL(24) 位运算(3) 其他(37) 动态规划(148) 区间(22) 图形打印(6) 图论(96) 字符串(39) 打表(13) 排序(31) 数学相关(153) 数据结构(73) 暴力解题(31) 机器学习(10) 栈(14) 树(51) 每周都有那么几天不想学习(2) 汇编(6) 知识点总结(17) 笔试试题(15) 网络流(7) 职场老油条(1) 计算几何(17) 贪心(62) 逐梦者(97) 郑州-大连(2) 问题残余(4) 骑行也是追梦(1)

/ 注册

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

蓝桥-BASIC-17-矩阵乘法

ACM模版描述题解模版题，矩阵快速幂，但是蓝桥不让带模版，还是自己手打吧！其实数据范围这么小，普通的矩阵乘法乘 M−1 次就行，完全没必要用矩阵快速幂，非但没有什么效率上的提升，说不定还会慢一些，但是我就是喜欢用矩阵快速幂…… 代码 #include <cstdio...

2021-05-21

0 431

图灵杯-第四届“图灵杯”NEUQ-ACM 程序设计竞赛-F-一道简单的递推题

ACM模版描述题解典型的矩阵快速幂问题，官方题解说需要用到滚动优化，是为了减少拷贝的次数……这里可以使用引用来减少拷贝，并且注意 long long，最开始输错了 0，不按套路出牌，竟然不是九个零，是十个！！！这里提供两个代码，都是矩阵快速幂，模版不同而已~~~ 做这个题也让我发现...

2021-05-21

0 419

51Nod-1359-循环探求

ACM模版描述题解这个题用到了蒙哥马利约化的知识，并且在这种高精度模幂时，我们只需要考虑剩余类环中的情况，大于这个的高位可以直接忽略掉，因为肯定可以被模消除，据说还用到了鸽舍原理，我也不是特别能理解这个题，官方题解有些不走心，公式难道是代码解析出问题了？怎么感觉残缺啊~~~ 这个代...

2021-05-21

0 248

51Nod-1379-索函数

ACM模版描述题解很容易就能证明，我们其实只需要求出第 n 项的位数，因为很明显经过这么多次或操作后全部为 1 。此时，我们应该想起来那个斐波那契数列的通项公式， fib(n)=15‾‾√[(1+5‾‾√2)n−(1−5‾‾√2)n] ...

2021-05-21

0 308

51Nod-TalkingData数据科学精英夏令营挑战赛-C-好数

ACM模版描述题解看着无数人 A 了这道题，我却还懵逼着……一开始模拟就模拟错了，坑死了。一开始看到有两分钟 A 掉这道题的人就知道这个是个套路题！赛后，用 OEIS 尝试搜索了一下，发现真得叼！！！可惜我以前竟然没有想过用这个伟大的工具…… 代码 #include ...

2021-05-21

0 333

51Nod-1383-整数分解为2的幂

ACM模版描述题解看到这里，我们应该可以想到，这是一个数论问题，应该是一个什么数列，暴力解出来小数据后，在 OEIS 中查看了一下下，发现的确是一个十分有趣的数列——Binary partition function: number of partitions of n into p...

2021-05-21

0 379

51Nod-1436-方程的解数

ACM模版描述题解既然讨论区有如此详尽的题解，我何不直接拿过来呢？这里说到无解的情况，其实也就是当 ai 取值总是小于 k 时，无解，换种说法就是 k≥2l ，这里存在溢出的问题，尽管使用 ULL ，同样无法避免当 l 为 64 ...

2021-05-21

0 405

hiho-hihoCoder挑战赛29-B-快速乘法

ACM模版描述题解一眼看到这个题就感觉见过，或者做过，但是就是想不起来在哪儿做过，然后就陷入了回忆杀……这是一个二幂拆分问题。赛后找了半天找到个不错的文章，专门讲编译器的这个优化。根据这个文章和一个前辈的代码改写了一个（代码 One）。这里需要注意的是，求出最少的项数 x 后...

2021-05-21

0 358

CF-Codeforces Round #420 (Div. 2)-E-Okabe and El Psy Kongroo

ACM模版描述题解这个题是矩阵快速幂问题，给定若干个上界，每个上界都是有一定宽度的，这些上界在 x 轴的投影是连续的，要我们从 (0,0) 移动到 (k,0) ，每次只能向右、右上、右下移动，所以呢，这个其实和《机器人走方格》有些相似，不过他是给定了连续的若干个矩形区域（...

2021-05-21

0 335

51Nod-1616-最小集合

ACM模版描述题解首先，用 vis[] 表示每一个数字的存在状态，然后枚举每一个不存在的数，一直枚举到 mx ，判断其所有倍数的 GCD 结果是否等于他，如果等于，那么一定是存在这个数的，否则就是不存在，然后累计结果就行了。看到官方题解比我的写法要快很多，判断次数少很多...

2021-05-21

0 354