欧拉函数

大家好，我是讯享网，很高兴认识大家。

刚开始入门欧拉函数

欧拉函数的公式：euler(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…(1-1/pn),其中p1,p2……pn为x的所有素因数，x是不为0的整数

(注意：每种质因数只一个。比如 12 = 2*2*3 那么 φ(12) = 12 * (1-1/2) * (1-1/3)=4

欧拉函数性质： 1、 φ(mn) = φ(m) φ(n)

2、若n为奇数，φ(2n) = φ(n)。

欧拉公式的延伸：一个数的所有质因子之和是euler(n)*n/2。

题目 hdu 1787 GCD Again

Problem Description

Do you have spent some time to think and try to solve those unsolved problem after one ACM contest?
No? Oh, you must do this when you want to become a "Big Cattle".
Now you will find that this problem is so familiar:
The greatest common divisor GCD (a, b) of two positive integers a and b, sometimes written (a, b), is the largest divisor common to a and b. For example, (1, 2) =1, (12, 18) =6. (a, b) can be easily found by the Euclidean algorithm. Now I am considering a little more difficult problem:
Given an integer N, please count the number of the integers M (0<M<N) which satisfies (N,M)>1.
This is a simple version of problem “GCD” which you have done in a contest recently,so I name this problem “GCD Again”.If you cannot solve it still,please take a good think about your method of study.
Good Luck!

Input

Input contains multiple test cases. Each test case contains an integers N (1<N<). A test case containing 0 terminates the input and this test case is not to be processed.

Output

For each integers N you should output the number of integers M in one line, and with one line of output for each line in input.

Sample Input

2 4 0

Sample Output

0 1

代码：

#include<bits/stdc++.h> using namespace std; int euler(int n) { int res=n; for(int i=2;i<=sqrt(n);i++) { if(n%i==0) res=res/i*(i-1);//res=res*(1-1/i) while(n%i==0) n/=i;//让n没有i 即这个素数只会出现一次 } if(n>1) res=res/n*(n-1);//n不等于一就表示还剩下一个素数 return res; } int main() { int n; while(cin>>n&&n) { cout<<n-euler(n)-1<<endl;//题目要求的是gcd(n,m)>1的个数 } return 0; }

讯享网

下面这个题用了欧拉公式的延伸：一个数的所有质因子之和是euler(n)*n/2。

hdu 3501 Calculation 2

Problem Description

Given a positive integer N, your task is to calculate the sum of the positive integers less than N which are not coprime to N. A is said to be coprime to B if A, B share no common positive divisors except 1.

Input

For each test case, there is a line containing a positive integer N(1 ≤ N ≤ ). A line containing a single 0 follows the last test case.

讯享网

Output

For each test case, you should print the sum module in a line.

Sample Input

3 4 0

Sample Output

0 2

代码：

讯享网#include<bits/stdc++.h> using namespace std; long long int euler(long long int n)//欧拉函数 { long long int res=n; for(long long int i=2;i<=sqrt(n);i++) { if(n%i==0) res=res/i*(i-1); while(n%i==0) n/=i; } if(n>1) res=res/n*(n-1); return res; } int main() { long long int n; while(cin>>n&&n) { cout<<((n-1)*n/2-n*euler(n)/2)%<<endl;//(n-1)*n/2是所有数之和 n*euler(n)/2是和n互质的数之和 } return 0; }

下面这个题是快速求欧拉函数（欧拉函数打表）

然后求出区间（a，b）的欧拉函数的值之后

hdu 2824 The Euler function

Problem Description

The Euler function phi is an important kind of function in number theory, (n) represents the amount of the numbers which are smaller than n and coprime to n, and this function has a lot of beautiful characteristics. Here comes a very easy question: suppose you are given a, b, try to calculate (a)+ (a+1)+....+ (b)

Input

There are several test cases. Each line has two integers a, b (2<a<b<).

Output

Output the result of (a)+ (a+1)+....+ (b)

Sample Input

3 100

Sample Output

讯享网

3042

代码：

#include<bits/stdc++.h> using namespace std; #define MAX  long long int e[MAX]; void eulor() { for(int i=1;i<MAX;i++) e[i]=i; for(int i=2;i<MAX;i++) { if(e[i]==i)//代表这个数是素数 { for(int j=i;j<MAX;j+=i) { e[j]=e[j]/i*(i-1);//把i这个数的倍数都进行一次相当于res=res/i*(i-1)的运算 } } } for(int i=2;i<MAX;i++) e[i]+=e[i-1];//叠加和 } int main() { eulor(); int a,b; while(cin>>a>>b) { cout<<e[b]-e[a-1]<<endl; } }

相关推荐