Q779的博客

OI模板-多项式快速傅里叶变换 FFT 传送门：快速傅里叶变换 FFT #include <bits/stdc++.h> using namespace std; // #define int long long // #defin

2024-02-21 OI

总结多项式

洛谷P3846 [TJOI2007] 可爱的质数/【模板】BSGS 题解题目链接：P3846 [TJOI2007] 可爱的质数/【模板】BSGS 题意：给定一个质数 \(p\)，以及一个整数 \(a\)，一个整数 \(b\)，现在要求

2024-02-21 OI

算法数学

离散对数在数论中，离散对数 (Discrete logarithm) 是基于原根的对数运算。离散对数在一些特殊情况下可以快速计算，然而通常没有非常快速的方法来计算它们。（比如模质数时）定义设 \(a\) 为模 \(m\) 的原根，

2024-02-21 OI

数学

洛谷P5810 [SCOI2004] 文本的输入题解题目链接：P5810 [SCOI2004] 文本的输入题意：人们在输入文本时，除了逐个输入这种方式外，还可以利用剪贴板进行复制，如果打入一个字母需要 \(1\) 的时间，将已输入

2024-02-20 OI

算法 DP

洛谷P1748 H数题解题目链接：P1748 H数题意：所谓 \(H\) 数，是指只含有 \(2,3,5,7\) 这些质因数的数，如 \(630\) 是 \(H\) 数，而 \(22\) 不是。现在要求输出第 \(n\) 个 \

2024-02-20 OI

算法数学 DP

洛谷P1306 斐波那契公约数题解题目链接：P1306 斐波那契公约数题意：对于 Fibonacci 数列： \[ f_i = f_{i - 1} + f_{i - 2} + [i = 1] \] 请求出 \(f_n\) 与 \(

2024-02-19 OI

算法数学

洛谷P9965 [THUPC 2024 初赛] 转化题解题目链接：P9965 [THUPC 2024 初赛] 转化题意：小 E 有 \(n\) 种颜色的球，其中第 \(i\) 种有 \(a_i\) 个。有两类工具，第一类可以把一个

2024-02-18 OI

算法

洛谷P2429 制杖题题解题目链接：P2429 制杖题题意：求不大于 \(m\) 的、质因数集与给定质数集有交集的自然数之和。输入格式：第一行，两个整数 \(n, m\)。第二行，\(n\) 个整数，表示质数集内的元素 \(

2024-02-16 OI

算法数学

洛谷P4980 【模板】Polya 定理题解题目链接：P4980 【模板】Polya 定理题意：给定一个 \(n\) 个点，\(n\) 条边的环，有 \(n\) 种颜色。给每个顶点染色，问有多少种本质不同的染色方案，答案对 \(

2024-02-14 OI

算法数学群论

Pólya 定理 Pólya 定理的中文名是波利亚计数定理。传送门：洛谷P4980 【模板】Polya 定理题解（在这篇文章里会讲解 Pólya 定理的运用）置换一个有限集合 \(S\) 到自身的双射称为 \(S\) 的一个置

2024-02-13 OI

数学群论

中国剩余定理 & 扩展鉴于之前写的中国剩余定理依托构思，现在重写一篇。中国剩余定理中国剩余定理(CRT)可求解如下形式的一元线性同余方程组 \[ \begin{cases} x \equiv a_1\ \pmod{p_1}

2024-02-09 OI

算法数学

群论基础在数学和抽象代数中，群论（Group Theory）主要研究叫做「群」的代数结构。群的定义在数学中，群（group）是由一种集合以及一个二元运算所组成的，符合「群公理」的代数结构。一个群是一个集合 \(G\) 加上对 \(

2024-02-07 OI

数学群论