UVA 12493 Stars (欧拉函数--求1~n与n互质的个数）-白红宇

UVA 12493 Stars (欧拉函数--求1~n与n互质的个数）

阅读量：6279 次

发布时间：2019-06-22

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

题目：

大致题意：圆上有偶数n个点。每m个点连起来。最后能够把全部点串联起来就合法。问有多少个m能够完毕串联，串联后形状同样的算反复

n <2^31

思路：能够写个暴力程序，能够发现仅仅要m与n互质，就能够完毕串联，所以用欧拉函数解决

证明：

设cnt为当第一次达到原点时连接了几个点。

所以有 m*cnt = k*n

得到 cnt = k*n/m

显然要第一次达到原点就是k逐渐增大使k*n/m变为整数的第一个k值，且由题意必须使cnt = n , 所以m与n互质就可以

所以m的种数就是 phi(n)

//#pragma comment(linker, "/STACK:1024000000,1024000000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #define SZ(x) ((int)(x).size())#define ALL(v) (v).begin(), (v).end()#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)#define reveach(i, v) for (__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++ i)#define REP(i,n) for ( int i=1; i<=int(n); i++ )#define rep(i,n) for ( int i=0; i< int(n); i++ )using namespace std;typedef long long ll;#define X first#define Y secondtypedef pair
                  
                    pii;typedef pair
                   
                     PII;template 
                    
                     inline bool RD(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) return 0; while (c != '-' && (c<'0' || c>'9')) c = getchar(); sgn = (c == '-') ? -1 : 1; ret = (c == '-') ? 0 : (c - '0'); while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0'); ret *= sgn; return 1;}template 
                     
                      inline void PT(T x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) PT(x / 10); putchar(x % 10 + '0');}int euler(int n){ //返回euler(n) int ans = n; int num = n; for(ll i = 2; i*i <= num; i++){ if( num%i == 0){ ans = ans/i*(i-1); while( num%i == 0) num /= i; } } if(num > 1) ans = ans/num*(num-1); return ans;}int main(){ int n; while(~scanf("%d",&n)){ printf("%d\n",euler(n)/2); }}