又是一道gcd题。。这题的欧拉函数貌似要暴力求。。
本来想把素数先筛出来的不过发现还慢些。。
那就暴力来吧。。复杂度不明然而跑得很快
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
// <2705.cpp> - 06/29/16 18:49:02 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; lol gl(){ lol res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=7e4; const int INF=1e9; lol lim; lol phi(lol x){ lol res=x; for(int i=2;i<=lim&&i<=x;i++){ if(x%i)continue; res=res/i*(i-1); while(!(x%i))x/=i; } if(x>1)res=res/x*(x-1); return res; } int main(){ lol n=gl(),ans=0;lim=sqrt(n); for(lol i=1;i<=lim;i++){ if(n%i)continue; ans+=i*phi(n/i); ans+=n/i*phi(i); } if(lim*lim==n)ans-=lim*phi(lim); printf("%lld",ans); return 0; } |
说点什么