HDU1695:GCD（容斥原理+欧拉函数+质因数分解）好题
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1695题目解析：Given 5 integers: a, b, c, d, k, you're to find x in a...b, y in c...d that GCD(x, y) = k.题目又说...
Trees in a Wood. UVA 10214 欧拉函数或者容斥定理 给定a,b求 |x|<=a, |y|<=b这个范围内的所有整点不包括原点都种一棵树。求出你站在原点向四周看到的树的数量/总的树的数量的值。
/**题目：Trees in a Wood. UVA 10214链接：https://vjudge.net/problem/UVA-10214题意：给定a,b求 |x|<=a, |y|<=b这个范围内的所有整点不包括原点都种一棵树。求出你站在原点向四周看到的树的数量/总的树的数量的值。思...
【BZOJ】2190 [SDOI2008]仪仗队（欧拉函数）
Description作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 现在，C君希望你告诉他队伍整齐时能看到的学生人数。Input共一个数N。Out...
BZOJ2095:[POI2010]Bridges(最大流,欧拉图)
DescriptionYYD为了减肥，他来到了瘦海，这是一个巨大的海，海中有n个小岛，小岛之间有m座桥连接，两个小岛之间不会有两座桥，并且从一个小岛可以到另外任意一个小岛。现在YYD想骑单车从小岛1出发，骑过每一座桥，到达每一个小岛，然后回到小岛1。霸中同学为了让YYD减肥成功，召唤了大风，由于是海...
hdu1286 寻找新朋友 （欧拉功能）
原标题：点击打开链接关于欧拉函数的算法具体解说：点击打开链接欧拉函数1.欧拉函数是不全然积性函数。2.欧拉函数p(x) = x * (p1 - 1) / p1 * (p2 - 1)/p2 * .....(pn - 1)/ pn;#include <iostream>#include &l...
BZOJ2818 欧拉函数
题意：求1--n中满足gcd(x,y)的值为质数的数对(x,y)的数目（ (x,y)和(y,x)算两个 ）sol：设p[i]是一个质数，那么以下两个命题是等价的：1.gcd(x,y)=12.gcd(x*p[i],y*p[i])=p[i]eg:gcd(36,25)=1，gcd(36*7,25*7)=7...
hdu 1116 Play on Words 欧拉路径+并查集
Play on WordsTime Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 7791 Accepted Submission(s): ...
UVa10820 Send a Table[欧拉函数]
Send a TableInput: Standard InputOutput: Standard OutputWhen participating in programming contests, you sometimes face the following problem: You know...
51nod 1237 最大公约数之和 V3【欧拉函数||莫比乌斯反演+杜教筛】
用mu写lcm那道卡常卡成狗(然而最后也没卡过去，于是写一下gcd冷静一下首先推一下式子\[\sum_{i=1}^{n}\sum_{j=1}^{n}gcd(i,j)\]\[\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{d=1}^{n}[gcd(i,j)==d]d\]\[\sum...
51nod 1227 平均最小公倍数【欧拉函数+杜教筛】
以后这种题能用phi的就不要用mu…mu往往会带着个ln然后被卡常致死把题目要求转换为前缀和相减的形式，写出来大概是要求这样一个式子：\[\sum_{i=1}^{n}\sum_{j=1}^{i}\frac{j}{gcd(i,d)}\]注意j的限制是i\[\sum_{d=1}^{n}\sum_{i=1...
BZOJ4916 神犇和蒟蒻 【欧拉函数 + 杜教筛】
题目很久很久以前，有一只神犇叫yzy;很久很久之后，有一只蒟蒻叫lty;输入格式请你读入一个整数N;1<=N<=1E9,A、B模1E9+7;输出格式请你输出一个整数A=\sum_{i=1}^N{\mu (i^2)};请你输出一个整数B=\sum_{i=1}^N{\varphi (i^2)...
51Nod.1237.最大公约数之和 V3(莫比乌斯反演 杜教筛 欧拉函数)
题目链接\(Description\)\(n\leq 10^{10}\)，求\[\sum_{i=1}^n\sum_{j=1}^ngcd(i,j)\ mod\ (1e9+7)\]\(Solution\)首先\[\sum_{i=1}^n\sum_{j=1}^ngcd(i,j)=\sum_{d=1}^nd...
【luogu3768】简单的数学题 欧拉函数(欧拉反演)+杜教筛
题目描述给出 $n$ 和 $p$ ，求 $(\sum\limits_{i=1}^n\sum\limits_{j=1}^nij\gcd(i,j))\mod p$ 。$n\le 10^{10}$ 。题解欧拉函数(欧拉反演)+杜教筛推式子：$$\begin{align}&\sum\limits_{...
BZOJ4916 神犇和蒟蒻（欧拉函数+杜教筛）
第一问是来搞笑的。由欧拉函数的计算公式容易发现φ(i2)=iφ(i)。那么可以发现φ(n2)*id(n)（此处为卷积）=Σd*φ(d)*(n/d)=nΣφ(d)=n2 。这样就有了杜教筛所要求的容易算前缀和的两个函数。一通套路即可。#include<iostream>#include&l...
bzoj 3944: Sum【莫比乌斯函数+欧拉函数+杜教筛】
一道杜教筛的板子题。两个都是积性函数，所以做法是一样的。以mu为例，设\( f(n)=\sum_{d|n}\mu(d) g(n)=\sum_{i=1}^{n}f(i) s(n)=\sum_{i=1}^{n}\mu(i) \)，然后很显然对于mu\( g(n)=1\)，对于phi\( g(n)=n*(...
Dirichlet's Theorem on Arithmetic Progressions POJ - 3006 线性欧拉筛
题意 给出a d n 给出数列 a,a+d,a+2d,a+3d......a+kd 问第n个数是几 保证答案不溢出直接线性筛模拟即可 #include<cstdio> #include<cstring> using namespace std; bool Is_Prim...
【51nod】1239 欧拉函数之和 杜教筛
【题意】给定n，求Σφ(i)，n<=10^10。【算法】杜教筛【题解】定义$s(n)=\sum_{i=1}^{n}\varphi(i)$杜教筛$\sum_{i=1}^{n}(\varphi *I)(i)=\sum_{i=1}^{n}\sum_{d|i}\varphi(d)=\sum_{i=1}...
bzoj 2005: [Noi2010]能量采集 筛法||欧拉||莫比乌斯
2005: [Noi2010]能量采集Time Limit: 10 Sec Memory Limit: 552 MB[Submit][Status][Discuss]Description栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后，栋栋再使用...
Applese涂颜色-欧拉降幂公式
链接：https://ac.nowcoder.com/acm/contest/330/E来源：牛客网题目描述精通程序设计的 Applese 叕写了一个游戏。在这个游戏中，有一个 n 行 m 列的方阵。现在它要为这个方阵涂上黑白两种颜色。规定左右相邻两格的颜色不能相同。请你帮它统计一下有多少种涂色的方...
POJ 2480 (约数+欧拉函数)
题目链接: http://poj.org/problem?id=2480题目大意：求Σgcd(i,n)。解题思路：如果i与n互质，gcd(i,n)=1，且总和=欧拉函数phi(n)。如果i与n不互质，那么只要枚举n的全部约数，对于一个约数d，若使gcd(i/d,n/d)互质，这部分的gcd和=d*欧...