标签 杜教筛 下的文章

  1. 首页
  2. 杜教筛

数论复习笔记

阶与原根 阶 定义 1.1 (阶) 对于 $m \in \mathbb{N}^*, a \in [0, m), (a, m) = 1$，设 $n$ 为满足 $a^n \equiv 1 \pmod{m}$ 的最小正整数，则称 $n$ 为 $a$ 模 $m$ 的阶，记做 $\delta_m(a)$。 关于阶，我们给出如下定理： 定理 1.1 $a, a^2, \cdots, a^{\del...

  • M_sea
  • 2021 年 04 月 05 日
  • 暂无评论

    • 洛谷3768 简单的数学题

    Luogu 分析 这样就很好杜教筛了。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #defi...

  • M_sea
  • 2020 年 06 月 15 日
  • 暂无评论

    • 杜教筛学习笔记

    一些前置知识 假设我们现在要求一个积性函数 $\mathbf{f}$ 的前缀和 $\mathbf{S}(n)$。 假设我们有一个奇妙的数论函数 $\mathbf{g}$，那么有 unordered_map<int,int> Mmu; int Smu(int n) { if (n<L) return mu[n]; if (Mmu.count(n)) retu...

  • M_sea
  • 2020 年 06 月 13 日
  • 6 条评论

    • 洛谷1587 [NOI2016]循环之美

    Luogu LOJ 分析 可以发现，$k$ 进制分数 $\frac{x}{y}$ 是纯循环的当且仅当 $\gcd(y,k)=1$。证明可以点这里。 另外为了避免算重，我们只统计最简分数。 那么我们要求的东西就是（设 $l=\min(n,m)$） 这样子直接枚举约数递归下去算即可；当 $k=1$ 时无法继续往下递归，但此时相当于要求 $\mu(i)$ 的前缀和，杜教筛即可。 代码 // ==...

  • M_sea
  • 2020 年 06 月 09 日
  • 暂无评论