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...
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...
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*(...
【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}...
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*欧...
欧拉函数（C语言实现）
欧拉函数（Euler's totient function）是指小于n的正整数中与n互质的数的数目，用φ(n)表示。特别的，φ(1)=1；例如：φ(10)=4；1 3 7 9与10互质。公式：φ(n)=n*(1-1/p(1))*(1-1/p(2))*(1-1/p(3))*...*(1-1/p(n))...
BZOJ2190 [SDOI2008]仪仗队（欧拉函数）
与HDU2841大同小异。设左下角的点为(1,1)，如果(1,1)->(x,y)和(1,1)->(x',y')向量平行，那只有在前面的能被看见。然后就是求x-1、y-1不互质的数对个数。而x或y等于1可以另外讨论一下，就是当n不等于1时就有两个，n等于1就特判一下。那么就用欧拉函数计数了...
【数论】【欧拉函数】【筛法求素数】【乘法逆元】【快速幂取模】bzoj2186 [Sdoi2008]沙拉公主的困惑
http://www.cnblogs.com/BLADEVIL/p/3490321.html http://www.cnblogs.com/zyfzyf/p/3997986.html 翻了翻题解，这两个合起来比较明白…… 题意：求1~n!中与m!互质的数的数量(mod R)。 ∵由欧几里得算法得...
【51nod1040】【最大公约数之和】【欧拉函数】
题目大意给出一个n，求1-n这n个数，同n的最大公约数的和。比如：n = 61,2,3,4,5,6 同6的最大公约数分别为1,2,3,2,1,6，加在一起 = 15解题思路 ans=∑x|nx∗∑ni=1gcd(i,n)==x => ans=∑x|nx∗∑ni=1gcd(i/...
PHP简单实现欧拉函数Euler功能示例
这篇文章主要介绍了PHP简单实现欧拉函数Euler功能,简单说明了欧拉函数的概念、原理,并结合实例形式分析了php实现欧拉函数的相关操作技巧,需要的朋友可以参考下
light1370 欧拉函数打表
/*给定n个数ai，要求欧拉函数值大于ai的最小的数bi求sum{bi}*/#include<bits/stdc++.h>using namespace std;#define maxn 1000005int n,a[maxn];int phi[maxn],m,v[maxn],prime...
欧拉函数和莫比乌斯反演（Mobius）
这几天研究了之前一直困扰自己很久的莫比乌斯反演，虽然自己现在学的还不是很好，就简简单单的写一下总结吧，咦，都没学会掌握我就写总结好像很欠揍，欧拉函数现在也系统的整理一下好了 一、欧拉函数 1.定义：在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。此函数以其首...