数论 - 欧拉函数模板题 --- poj 2407 : Relatives

简介: Relatives Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 11372   Accepted: 5544 Description Given n, a positive in...
Relatives
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 11372   Accepted: 5544

Description

Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz.

Input

There are several test cases. For each test case, standard input contains a line with n <= 1,000,000,000. A line containing 0 follows the last case.

Output

For each test case there should be single line of output answering the question posed above.

Sample Input

7
12
0

Sample Output

6
4

Source

 

 

 

Mean: 

 输入一个正整数n,求小于n的所有数中与n互质的数的个数。

analyse:

 裸的欧拉函数,数据很弱,直接用模板。

 

欧拉函数PHI(n)表示的是比n小,并且与n互质的正整数的个数(包括1)。比如:
PHI(1) = 1; PHI(2) = 1; PHI(3) = 2; PHI(4) = 2; ... PHI(9) = 6; ...

 

要计算一个数的欧拉函数的方法如下:

1)将这个数分解质因数:n=p1^k1+p2^k2+p3^k3+p4^k4....

2) PHI(n) = (p1 ^ k1 - p1 ^ (k1 - 1)) * (p2 ^ k2 - p2 ^ (k2 - 1)) * ... * (pn ^ kn - pn ^ (kn - 1))
              = Mult { pi ^ ki - pi ^ (ki -1) };

证明过程如下:
1. 容易想到:当n为素数时,PHI(n) = n - 1。因为每个比n小的正整数都和n互素。当n为素数p的k次方时,PHI(n) = p ^ k - p ^ (k - 1)。因为在1到n之间的正整数只有p的倍数和n不互素,这样的数有(p ^ k / p)个。
2. 如果m和n互素,即GCD(m, n) = 1,那么PHI(m * n) = PHI(m) * PHI(n)。用中国剩余定理可以证明,证明的思路是建立这样一种一一对应的关系(a, b) <-> x,其中正整数a小于m并且gcd(a, m) = 1,正整数b小于n并且gcd(b, n) = 1,正整数x小于m*n并且gcd(m*n, x) = 1。证明过程如下:
    1)根据中国剩余定理,如果m和n互素,那么关于未知量x的方程组x % m = a, x % n = b(0 <= a < m, 0 <= b < n),当0 <= x < m * n时存在并且仅存在一个解。容易证明,如果两个这样的方程组有相同的m, n但是a, b不同,那么他们的解x一定不同。
    2)首先用反正法证明:gcd(m, a) = 1且gcd(n, b) = 1是gcd(m*n, x) = 1的必要条件:假设gcd(a, m) = k > 1,由此可得:a = a' * k; m = m' * k => x = k' * m + a = k' * k * m' + k * a' = k * (k' * m' + a'); 所以gcd(x, m) = k > 1。同理可证,如果gcd(b, n) > 1, 那么gcd(x, n) > 1。所以x和m * n互素的必要条件是a和m互诉且b和n互素。
    3)接下来我们证明充分性:由x % m = a 可以得到x = k * m + a;由欧几里德算法求最大公约数的过程(就不证明了,呵呵,还得想)可以知道gcd(x, m) = gcd(m, a) = 1;同理可得,如果gcd(n, b) = 1那么gcd(x, n) = 1。接下来很容易得到:gcd(m*n, x) = 1。从而证明了充分性。
    4)上面三步的结论表明,数对(a, b)是可以和x建立起一一对应的关系的,所以有多少个不同的(a, b),就有多少个不同的x。
3.将n分解成素数乘积后,显然对于任意的i, j(i != j)都满足 pi ^ ki和pj ^ kj是互素的,于是可以的到上面的公式。

跟据上面的公式,可以得到关于欧拉函数的递推关系:
假设素数p能整除n,那么
如果p还能整除n / p, PHI(n) = PHI(n / p) * p;
如果p不能整除n / p, PHI(n) = PHI(n / p) * (p - 1);

 

Time complexity:O(n)

 

Source code:

 

// Memory   Time
// 1347K     0MS
// by : Snarl_jsb
// 2014-09-12-21.18
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<climits>
#include<cmath>
#define N 1000010
#define LL long long
using namespace std;


int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}

inline int lcm(int a,int b){
	return a/gcd(a,b)*b;
}

int eular(int n)    ////求1..n-1中与n互质的数的个数
{
	int ret=1,i;
	for (i=2;i*i<=n;i++)
		if (n%i==0){
			n/=i,ret*=i-1;
			while (n%i==0)
				n/=i,ret*=i;
		}
	if (n>1)
		ret*=n-1;
	return ret;
}
int main()
{
//    freopen("C:\\Users\\ASUS\\Desktop\\cin.cpp","r",stdin);
//    freopen("C:\\Users\\ASUS\\Desktop\\cout.cpp","w",stdout);
    int n;
    while(~scanf("%d",&n),n)
    {
        int ans=eular(n);
        cout<<ans<<endl;
    }

    return 0;
}

  

目录
相关文章
|
算法
POJ 3154 Graveyard【多解,数论,贪心】
Graveyard Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 1707   Accepted: 860   Special Judge Description Prog...
1249 0
|
Java 机器学习/深度学习
UESTC 30 &&HDU 2544最短路【Floyd求解裸题】
最短路 Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 65817    Accepted Submission(s): 28794 Problem Description 在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。
1150 0
|
人工智能 算法
洛谷 P2312 解方程
题目描述 已知多项式方程: $a_0+a_1x+a_2x^2+..+a_nx^n=0$//用LaTex好看多了 求这个方程在[1, m ] 内的整数解(n 和m 均为正整数) 输入输出格式 输入格式:   输入文件名为equation .in。
612 0
poj-2909-哥德巴赫猜想
Description For any even number n greater than or equal to 4, there exists at least one pair of prime numbers p1 and p2 such that n = p1 + p2 This conjecture has not been proved nor refused yet.
801 0
数论 + 公式 - HDU 4335 What is N?
What is N?  Problem's Link:  http://acm.hdu.edu.cn/showproblem.php?pid=4335   Mean:  给你三个数b、P、M,让你求有多少个n满足下式。
862 0
数学 --- 高斯消元 POJ 1830
开关问题  Problem's Link: http://poj.org/problem?id=1830   Mean:  略 analyse: 增广矩阵:con[i][j]:若操作j,i的状态改变则con[i][j]=1,否则con[i][j]=0。
976 0
hdu 1695 GCD【欧拉函数+容斥原理】
GCD Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6253    Accepted Submission(s): 2...
1040 0
|
Java Go
组合数学 - 母函数的运用 --- 模板题
Holding Bin-Laden Captive! Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 15064    Accepted ...
1118 0