搜索结果
查询Tags标签： 欧拉，共有 55条记录-
欧拉路径学习笔记
\(\bigstar\) 欧拉路径 若 \(G=(V,\ E)\) 中的一条路径包含了 \(E\) 中的所有边且不重复，则称其为 欧拉路径（\(\textbf{Eulerian Path}\)）。 若该路径的起点与终点相同，则称其为 欧拉回路（\(\textbf{Eulerian Circuit}\)）。 欧拉路径的存在条件：此图连通；对于无向…
2022/8/15 6:26:39 人评论 次浏览 -
qemu运行欧拉/鸿蒙
qemu运行openeuler-riscv64 参考[https://zhuanlan.zhihu.com/p/440896294]运行了qemu-openeuler 导出容器(可以不看这里)docker export导出的是容器的快照，不会保存元数据,所以，如果你想让其他人也使用也就需要使用docker save，docker save是针对镜像的，所以我们需要…
2022/8/13 6:23:03 人评论 次浏览 -
倍增，DFS序，欧拉序和树的一些知识
倍增 定义 倍增法,顾名思义就是翻倍. 它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度 这个方法在很多算法中均有应用，其中最常用的是 RMQ 问题和求LCA，无修改的路径信息。 路径最小值 注意:路径上的信息需要可以合并,例如求最值 const int N = 201000; co…
2022/8/11 6:26:54 人评论 次浏览 -
祖孙询问 用欧拉序列转化为 RMQ 问题
分析 N 个点，按照欧拉序给它们排序到一个数组里（数组长度是2*（N-1） + 1 = 2*N-1），并标记每个节点第一次出现的位置，st表处理欧拉序节点的最小深度。 查询（u，v） 找到两个节点第一次所在的位置，再从st表中找到这两个位置间的最小深度。欧拉序：每经过一次该节点记…
2022/8/5 23:22:47 人评论 次浏览 -
筛法求欧拉函数之和
题目描述 求\(1\sim n\)每个数欧拉函数之和 想法如果\(i\)是质数 \(\varphi (i) = i - 1\)质数\(i\)只有\(1\)和\(i\)两个因数，\(i\)不和\(i\)本身互质，因数只有一个\(1\)，所以互质的数就有\(i-1\)个如果\(i\)不是质数\(i \% j = 0\) \(j\)是质数 则\(j\)即\(i\)的一个…
2022/7/24 6:24:07 人评论 次浏览 -
欧拉函数
给定 \(n\) 个正整数 \(a_i\)，请你求出每个数的欧拉函数。 欧拉函数的定义$ 1 \sim N $ 中与 $ N $ 互质的数的个数被称为欧拉函数，记为 $ ϕ(N) \(。 若在算数基本定理中，\) N = p_1{a_1}p_2{a_2}…p_m^{a_m} \(，则： \) ϕ(N) $ = $ N \times \frac{p_1-1}{p_1}…
2022/7/24 6:24:05 人评论 次浏览 -
自然对数的底数e
自然对数底数e的来源_哔哩哔哩_bilibili 注解： 1.欧拉给了这个数字一个名字，叫做e。
2022/6/9 23:49:41 人评论 次浏览 -
noip模拟26
T1. LCIS 数组开小 100pts->60pts 蓝书原题，决策集合最优化\(O（n^2）\) 我用的树（状数组）套树（装数组） 与 值域优化对冲，导致达不到\(O(n ^ 2 (logn) ^2)\)的复杂度，lyin试图卡掉以失败告终 最坏复杂度\(O(n^2 logn )\),好多人\(O(n^4)\)跑得飞快 T2.物流运输 …
2022/6/7 23:23:00 人评论 次浏览 -
【欧拉函数】AcWing873. 欧拉函数——欧拉函数的证明与代码
AcWing873.欧拉函数证明与题解#include <iostream>using namespace std;int phi(int x) {int res = x;for(int i = 2; i <= x / i; ++i){if(x % i == 0){res = res / i * (i - 1); //先除后乘防止爆intwhile(x % i == 0) x /= i;}}if(x > 1) res = res / x *…
2022/6/7 23:22:42 人评论 次浏览 -
有向图与无向图：欧拉路径&欧拉回路（一笔画）
咕了好久的图论的一小小小部分。 1、定义 欧拉路径 ：不重复经过图上每一条边的路径 欧拉回路 ： 起止点相同的欧拉路径 2、判定 $\bullet$ 有向图：$\bullet$ 欧拉路径 ：图中有且仅有 $1$ 个点出度比入度多 $1$ ，为起点；图中有且仅有 $1$ 个点入度比出度多 $1$ ，为…
2022/4/20 23:19:24 人评论 次浏览 -
题单：数学
1.burnside 定理，polya 计数法 简单题：2409 -- Let it Bead (poj.org)2154 -- Color (poj.org)1286 -- Necklace of Beads (poj.org) 强烈推荐：2888 -- Magic Bracelet (poj.org)2. 置换，置换的运算 简单题3207 -- Ikkis Story IV - Pandas Trick (poj.org)1026 -- …
2022/4/9 23:21:11 人评论 次浏览 -
[模板] BEST 定理
一、题目 点此看题 二、解法 这篇博客主要记录我的感性理解，相信能帮助你直观地理解 \(\tt BEST\) 定理。 首先对于一条欧拉路径，我们考虑保留每个点的最后一条出边。可以证明出边一定构成一棵内向树，我们只需要证明不会构成环，而如果构成环，考虑走完环的最后一条出边…
2022/3/8 23:47:01 人评论 次浏览 -
质数筛与欧拉函数
第一课时 复习及引入 质数判断 bool isPrime(int x){if(x<2) return false;for(int i=2;i*i<=x;i++){if(x%i==0) return false;}return true; }复杂度分析 \(O(\sqrt{n})\) 引入问题，输入n(\(1\leq n\leq10^6\))个数字(\(0\leq x \leq 10^6\))，判断每个数是不是质…
2022/3/8 23:16:30 人评论 次浏览 -
欧拉回路与欧拉路径
欧拉路径和欧拉回路哥尼斯堡七桥问题以下内容摘自《信息学奥赛一本通提高篇》.欧拉回路问题是图论中最古老的问题之一。它诞生于18世纪的欧洲古城哥尼斯堡，普瑞格尔河流经这座城市，人们在两岸以及河中间的小岛之间建了7座桥，如下图所示：七桥问题图示市民们喜欢在这里散…
2022/2/1 7:01:12 人评论 次浏览 -
算法竞赛—欧拉筛素数（线性筛）
int n;//求1 ~ n之间的素数 int prime[N],cnt;//prime数组存放素数 cnt为prime的长度 int st[N];//数字i是否为素数void euler(){for(int i=2;i<=n;i++){if(!st[i]){prime[++cnt]=i;}for(int j=1;j<=cnt&&prime[j]<=n/i;j++){st[i*prime[j]]=1;if(i%prim…
2022/1/30 17:11:39 人评论 次浏览
