欧拉函数和莫比乌斯反演（Mobius）
这几天研究了之前一直困扰自己很久的莫比乌斯反演，虽然自己现在学的还不是很好，就简简单单的写一下总结吧，咦，都没学会掌握我就写总结好像很欠揍，欧拉函数现在也系统的整理一下好了 一、欧拉函数 1.定义：在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。此函数以其首...
BZOJ 2818 Gcd(欧拉函数+质数筛选）
2818: GcdTime Limit: 10 Sec Memory Limit: 256 MBSubmit: 9108 Solved: 4066[Submit][Status][Discuss]Description给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的数对(x...
POJ2513 Colored Sticks(欧拉)
题目链接。题目大意：给很多木棍，两端被涂了颜色。任意两根木棍的相同颜色处可以拼接在一起，问有没有可能将所有的木棍都连起来，成一条直线？分析：考点，欧拉道路。将一根木棍看成一条边，两端的颜色看成两个点，问题成了，能否从无向图的一个结点出发走出一条道路，每条边恰好经过一次。求法：如果一个无向图是连通的，...
HDU 4676 Sum Of Gcd 【莫队 + 欧拉】
任意门：http://acm.hdu.edu.cn/showproblem.php?pid=4676Sum Of GcdTime Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total ...
poj2478 Farey Sequence (欧拉函数)
Farey Sequence题意：给定一个数n，求在[1,n]这个范围内两两互质的数的个数。（转化为给定一个数n，比n小且与n互质的数的个数）知识点：欧拉函数：普通求法：int Euler(int n){ int ans=n; for(int i=0;i<cnt&&...
poj2478 Farey Sequence 欧拉函数的应用
仔细看看题目，按照题目要求 其实就是 求 小于等于n的 每一个数的 欧拉函数值 的总和，为什么呢，因为要构成 a/b 然后不能约分 所以 gcd(a,b)==1，所以 分母 b的 欧拉函数值 就是 以b为分母的 这样的数有几个，分母b的范围 是小于等于n，所以 直接套一个模版就可以了 ，网上...
51Nod 1239 欧拉函数前n项和 杜教筛
http://www.51nod.com/Challenge/Problem.html#!#problemId=1239AC代码#include <bits/stdc++.h>#define pb push_back#define mp make_pair#define fi first...
BZOJ.3884.上帝与集合的正确用法(扩展欧拉定理)
\(Description\)给定p，\(Solution\)欧拉定理：\(若(a,p)=1\),则\(a^b\equiv a^{b\%\varphi(p)}(mod\ p)\).扩展欧拉定理：\(a^b\equiv a^{b\%\varphi(p)+\varphi(p)}(mod\ p)\) (a...
操作系统产业峰会 2022 召开在即，欧拉重磅发布抢先看
如今，数字经济成为全球经济增长的主引擎。基础软件是数字经济发展的基础，是制造强国、网络强国、数字中国建设的关键支撑。而基础软件中的操作系统，作为数字基础设施的底座，已经成为推动产业数字化、智能化发展的核心力量。 2022年12月28-29日，以“立根铸魂 崛起数智时代”为主题的操作系统产业峰会202...
BZOJ2705 SDOI2012 Longge的问题 【欧拉函数】
BZOJ2705 SDOI2012 Longge的问题DescriptionLongge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。Input一个整数，为N。Output一个整数，为所求的答案。S...
费马小定理&欧拉定理
在p是素数的情况下，对任意整数x都有xp≡x(mod p)。这个定理被称作费马小定理其中如果x无法被p整除，我们有xp-1≡1(mod p)。利用这条性质，在p是素数的情况下，就很容易求出一个数的逆元。那上面的式子变形之后得到a-1≡ap-2(mod p)，因此可以通过快速幂求出逆元。我们先来证明一...
UVALive-3263 That Nice Euler Circuit （几何欧拉定理）
https://vjudge.net/problem/UVALive-3263 平面上有一个n个端点的一笔画，第n个端点总是和第一个端点重合，因此图示一条闭合曲线。 组成一笔画的线段可以相交，但不会部分重叠，求这些线段将平面分为几部分 包括封闭区域和无限大区域 欧拉定理：平面图的顶点数V，边...
HDU 1695 GCD（欧拉函数+容斥原理）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1695题意：x位于区间[a, b]，y位于区间[c, d]，求满足GCD(x, y) = k的(x, y)有多少组，不考虑顺序。思路：a = c = 1简化了问题，原问题可以转化为在[1, b/k]和[1...
HDU 1787 GCD Again(欧拉函数，水题)
GCD AgainTime Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1997 Accepted Submission(s): 772Pr...
HDU 5430 Reflect（欧拉函数）
题目： http://acm.hdu.edu.cn/showproblem.php?pid=5430从镜面材质的圆上一点发出一道光线反射NNN次后首次回到起点。问本质不同的发射的方案数。输入描述第一行一个整数T，表示数据组数。T≤10T \leq 10T≤10对于每一个组，共一行，包含一个整数，表示...
大数取模：一般取模+技巧取模+快速幂取模+欧拉函数(费马小定理)
一般取模运算(不推荐)： (a^n)%m。 我们可以改写为(a^n)%m= (（a%m)^n)%m, 即循环n次。 缺点：低效，循环了n次。 int exp_mod(int a,int n,int m){ a = a%m;int temp = 1;while(n--) { ...
HDU5597/BestCoder Round #66 (div.2) GTW likes function 打表欧拉函数
GTW likes function Memory Limit: 131072/131072 K (Java/Others) 问题描述 现在给出下列两个定义：f(x)=f_{0}(x)=\sum_{k=0}^...
hdu 5597GTW likes function(欧拉函数)
题目链接：【hdu 5597】 f(n)=sum((-1)^k * 2^(2n-2k) * C(k, 2n-k+1)) 0<=k<=n 这个公式化简之后就是f(x) = x+1 简单证明一下 首先要知道C(m,n)+C(m+1, n) = C(m+1, n+1) <span...
LCA-RMQ+欧拉序
还是那一道洛谷的板子题来说吧传送门其实好几天之前就写了结果dr实在是太弱了没有那么多的精力于是就一直咕咕咕了哎今天终于补上来了LCA概念传送门RMQ传送门这个算法是基于RMQ和欧拉序的算法什么是Rmq？ RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A...
POJ 3090 Visible Lattice Points 【欧拉函数】
<题目链接>题目大意：给出范围为(0, 0)到(n, n)的整点，你站在(0,0)处，问能够看见几个点。解题分析：很明显，因为 N (1 ≤ N ≤ 1000) ，所以无论 N 为多大，(0,1),(1,1),(1,0)这三个点一定能够看到，除这三个点以外，我们根据图像分析可得，设一个点...