传送门：点击打开链接
题意：对于n个点围成的圈。从一个点出发，顺时针数K个位置，一直进行这个操作直到回到最初的那个点时，恰好把所有的点都访问了一遍，问最大的K(K<=n/2)
思路：很容易就想到了一种方法，找到K<=n/2，且gcd(K,n)=1，有人是用java从n/2向1去枚举的，感觉好暴力，所以当时不敢这样写
后来发现其实是有规律的，从n=3一直算下去，会得到一个这样的序列1 1 2 1 3 3 4 3 5 5 6 5 7 7 8 7 9 9 10 9.....
很明显以4个为一组，一下子就能找到规律。。
然后按照这个规律直接算出答案就行了
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 2500;
const int MAXN = 9999;
const int DLEN = 4;class Big {
public:int a[MX], len;Big(const int b = 0) {int c, d = b;len = 0;memset(a, 0, sizeof(a));while(d > MAXN) {c = d - (d / (MAXN + 1)) * (MAXN + 1);d = d / (MAXN + 1);a[len++] = c;}a[len++] = d;}Big(const char *s) {int t, k, index, L, i;memset(a, 0, sizeof(a));L = strlen(s);len = L / DLEN;if(L % DLEN) len++;index = 0;for(i = L - 1; i >= 0; i -= DLEN) {t = 0;k = i - DLEN + 1;if(k < 0) k = 0;for(int j = k; j <= i; j++) {t = t * 10 + s[j] - '0';}a[index++] = t;}}Big operator/(const int &b)const {Big ret;int i, down = 0;for(int i = len - 1; i >= 0; i--) {ret.a[i] = (a[i] + down * (MAXN + 1)) / b;down = a[i] + down * (MAXN + 1) - ret.a[i] * b;}ret.len = len;while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;return ret;}bool operator>(const Big &T)const {int ln;if(len > T.len) return true;else if(len == T.len) {ln = len - 1;while(a[ln] == T.a[ln] && ln >= 0) ln--;if(ln >= 0 && a[ln] > T.a[ln]) return true;else return false;} else return false;}Big operator+(const Big &T)const {Big t(*this);int i, big;big = T.len > len ? T.len : len;for(i = 0; i < big; i++) {t.a[i] += T.a[i];if(t.a[i] > MAXN) {t.a[i + 1]++;t.a[i] -= MAXN + 1;}}if(t.a[big] != 0) t.len = big + 1;else t.len = big;return t;}Big operator-(const Big &T)const {int i, j, big;bool flag;Big t1, t2;if(*this > T) {t1 = *this;t2 = T;flag = 0;} else {t1 = T;t2 = *this;flag = 1;}big = t1.len;for(i = 0; i < big; i++) {if(t1.a[i] < t2.a[i]) {j = i + 1;while(t1.a[j] == 0) j++;t1.a[j--]--;while(j > i) t1.a[j--] += MAXN;t1.a[i] += MAXN + 1 - t2.a[i];} else t1.a[i] -= t2.a[i];}t1.len = big;while(t1.a[t1.len - 1] == 0 && t1.len > 1) {t1.len--;big--;}if(flag) t1.a[big - 1] = 0 - t1.a[big - 1];return t1;}int operator%(const int &b)const {int i, d = 0;for(int i = len - 1; i >= 0; i--) {d = ((d * (MAXN + 1)) % b + a[i]) % b;}return d;}Big operator*(const Big &T) const {Big ret;int i, j, up, temp, temp1;for(i = 0; i < len; i++) {up = 0;for(j = 0; j < T.len; j++) {temp = a[i] * T.a[j] + ret.a[i + j] + up;if(temp > MAXN) {temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);up = temp / (MAXN + 1);ret.a[i + j] = temp1;} else {up = 0;ret.a[i + j] = temp;}}if(up != 0) {ret.a[i + j] = up;}}ret.len = i + j;while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;return ret;}void print() {printf("%d", a[len - 1]);for(int i = len - 2; i >= 0; i--) printf("%04d", a[i]);}
};int main() {char word[MX];while(~scanf("%s", word)) {Big n(word);Big a = (n - 3) / 4 + 1;Big b = a * 2 - 1;Big c = n - a * 4 + 2;if(c.a[0] == 3) (b + 1).print();else b.print();printf("\n");}return 0;
}