题意很明确,比n小且与n互质的数的个数
欧拉函数就是用来解决这个的
首先要知道 【定理】正整数n(n≥2)可以唯一分解成素数乘积,即:n =p[1]^r1 * p[2] ^r2 * p[3]^r3. *...* p[s]^rs
其次欧拉函数有两个性质,可以用来编程,单独求phi函数:
① Ø(m) = m ( 1- 1/p[1]) ( 1- 1/p[2])…( 1- 1/p[s])
② Ø(p^k) = p^k – p^(k-1) = (p-1)p^(k-1)
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 305
#define INF 100000000
#define eps 1e-7
#define PI 3.1415926535898
using namespace std;
int euler(int n)
{
int x = n;
int i;
int phi = n;
for (i = 2; i * i <= x; i++)
{
if (x % i == 0)
{
phi = phi / i * (i - 1) ;
while (x % i == 0) x /= i;
}
}
if (x != 1) phi = phi / x * (x - 1);
return phi;
}
int main()
{
int n;
while(scanf("%d", &n) != EOF && n)
{
printf("%d\n", euler(n));
}
return 0;
}
下面是预处理打表的
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 305
#define INF 100000000
#define mod 1000000007
#define eps 1e-7
#define PI 3.1415926535898
using namespace std;
int phi[100001];
void euler()
{
phi[1] = 1;
for(int i = 2; i <= 100000; i++)
if(!phi[i])
{
for(int j = i; j <= 100000; j += i)
{
if(!phi[j]) phi[j] = j;
phi[j] = phi[j] / i * (i - 1);
}
}
}
int main()
{
euler();
int T, n;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
printf("%d\n", phi[n]);
}
return 0;
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
北大POJ2002-Squares 解题报告+AC代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
Poj中一些题目的源代码,里面共有二十多道题目,OI
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码