UVA 12493-Stars(欧拉函数)-白红宇

UVA 12493-Stars(欧拉函数)

阅读量：2029 次

发布时间：2019-04-28

本文共 743 字，大约阅读时间需要 2 分钟。

题目地址：

题意：圆上有N个点把圆分成N等分，求隔相同的点能一笔画完所有点的方法

思路：要一笔画出，那么（N，K）必定没有在中间相交，而只能在起始位置（把K当作是K等分），所以K就是与N互质的个数，又因为K=1和K=N-1，结果是一样的，所以最后的结果除以2。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #pragma comment(linker, "/STACK:102400000,102400000")using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const double pi= acos(-1.0);const double esp=1e-6;using namespace std;LL Euler(LL n){ //LL m=floor(sqrt(n+0.5)); LL ans=n; for(LL i=2;i*i<=n;i++){ if(n%i==0){ ans=ans/i*(i-1); while(n%i==0) n/=i; } } if(n>1) ans=ans/n*(n-1); return ans;}int main(){ LL n; while(~scanf("%lld",&n)){ printf("%lld\n",Euler(n)/2); } return 0;}