放牧代码和思想
专注自然语言处理、机器学习算法
    时间有限,只有GitHub上的issue能及时处理,大约每周末一次。另外,不要叫我楼主,谢谢。

POJ 2407 Relatives 题解《挑战程序设计竞赛》

目录

POJ 2407 Relatives 

欧拉函数:求少于或等于n的数中与n互素的数的个数;n <= 1,000,000,000。

4.1更加复杂的数学问题 

计数 

就是裸的欧拉……函数嘛。

唠唠嗑,最近发生好多事情。感觉公司里大家往往很关心算法的效果,但并不怎么关心算法的速度,反正上Hadoop集群,并行化似乎是万金油的样子

#include <iostream>
using namespace std;

//return phi(n) , 复杂度O(sqrt(n))
inline int phi(int x)
{
	int ret = x;
	for (int i = 2; i * i <= x; i++)
	{
		if (x % i == 0)
		{
			ret = ret / i * (i - 1);
			for (; x % i == 0; x /= i);
		}
	}
	if (x != 1)
	{
		ret = ret / x * (x - 1);
	}
	return ret;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n;
	while (~scanf("%d", &n) && n)
	{
		printf("%d\n", phi(n));
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////
14445149 hankcs 2407 Accepted 132K 0MS C++ 731B 2015-07-21 19:53:04

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 2407 Relatives 题解《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机