Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

程序有,自己看,重点看分界线。

Posted by 3552981944 at 2018-08-14 19:09:58 on Problem 2407
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iomanip>
using namespace std;
int num[20000],l;

void done()
{
	int i,j,k;
	l=2;
	num[1]=2;num[2]=3;
	for (i=5;i<=65535;i+=2)
	{
		k=sqrt(i);
		for (j=1;j<=l;j++)
		{
			if (i%num[j]==0) break;
			if (num[j]>k) {l++,num[l]=i;break;}
		}
	}
}

int kkk(int x)
{
	int i,ans=x;
	int k=sqrt(x);
	for (i=1;i<=l;i++)
	{
		if (num[i]>k) break;
		if(x%num[i]==0)
		{
			ans=(ans/num[i])*(num[i]-1);
			while(x%num[i]==0) x/=num[i];
		}
		if (x==1) break;
	}
	if(x>1) ans=(ans/x)*(x-1);
	return ans;
}

int main(){
//	freopen (".in","r",stdin);
//	freopen (".out","w",stdout);
	
	done();
	int ans,n;
	while (scanf("%d",&n))
	{
		if (n==0) break;
		ans=kkk(n);
		printf("%d\n",ans);
	}
	
	fclose (stdin);
	fclose (stdout);
	return 0;
}
/**/
#include <cstdio>
#include <cmath>
using namespace std;
int pri[9000],px;

void prime()
{
	int k;
	bool flag;
	pri[1]=2;
	px=1;
	for(int i=3;i<=65535;i+=2)
	{
		flag=1;k=sqrt(i);
		for(int j=2;j<=k;j++)
			if(i%j==0) {flag=0;break;}
		if(flag) pri[++px]=i;
	}
}

int n;

int get_ans(int n)
{
	int i=1,res=n;
	while(i<=px&&n>1)
	{
		if(n%pri[i]==0)
		{
			res=(res/pri[i])*(pri[i]-1);
			while(n%pri[i]==0) n/=pri[i];
		}
		i++;
	}
	if(n>1) res=(res/n)*(n-1);
	return res;
}

int main()
{
	//freopen("poj.in","r",stdin);
	prime();
	while(scanf("%d",&n)==1&&n)
	{
		printf("%d\n",get_ans(n));
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator