https://uva.onlinejudge.org/index.phpoption=com_onlinejudge&Itemid=8&category=279&page=show_problem&problem=3937
题目：
大致题意：圆上有偶数n个点，每间隔m个点连起来，最后可以把所有点串联起来就合法。问有多少个m可以完成串联，串联后形状相同的算重复
n <2^31
思路：可以写个暴力程序，，可以发现只要m与n互质，就可以完成串联，所以用欧拉函数解决
//#pragma comment(linker, "/STACK:1024000000,1024000000")#include <iostream>#include <cstring>#include <cmath>#include <queue>#include <stack>#include <map>#include <set>#include <string>#include <vector>#include <cstdio>#include <ctime>#include <bitset>#include <algorithm>#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<int,int> pii;typedef pair<pii,pii> PII;template <class T>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 <class T>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);}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
海阔凭鱼跃，天高任鸟飞。我要加油，冲向我的理想。
