Relatives(poj2407)(求大数的欧拉函数模板题)
发布时间:2020-12-14 02:19:38 所属栏目:大数据 来源:网络整理
导读:Link:http://poj.org/problem?id=2407 Relatives Time Limit: ?1000MS ? Memory Limit: ?65536K Total Submissions: ?12582 ? Accepted: ?6144 Description Given n,a positive integer,how many positive integers less than n are relatively prime to n?
Link:http://poj.org/problem?id=2407
AC code: #include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<cmath> #include<queue> #include<map> #include<stack> #include<vector> #define LL long long #define MAXN 100010 using namespace std; //直接求解欧拉函数 int euler(int n){ //返回euler(n) int res=n,a=n; for(int i=2;i*i<=a;i++){ if(a%i==0){ res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出 while(a%i==0) a/=i; } } if(a>1) res=res/a*(a-1); return res; } int main() { int n; while(~scanf("%d",&n)) { if(n==0) break; printf("%dn",euler(n)); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |