Chinese Girls' Amusement
Time Limit:1000MS Memory Limit:64000KB 64bit IO Format:%lld & %llu
Description
You must have heard that the Chinese culture is quite different from that of Europe or Russia. So some Chinese habits seem quite unusual or even weird to us.
So it is known that there is one popular game of Chinese girls. N girls stand forming a circle and throw a ball to each other. First girl holding a ball throws it to the K-th girl on her left (1 ≤ K ≤ N/2). That girl catches the ball and in turn throws it to the K-th girl on her left, and so on. So the ball is passed from one girl to another until it comes back to the first girl. If for example N = 7 and K = 3, the girls receive the ball in the following order: 1, 4, 7, 3, 6, 2, 5, 1.
To make the game even more interesting the girls want to choose K as large as possible, but they want one condition to hold: each girl must own the ball during the game.
So it is known that there is one popular game of Chinese girls. N girls stand forming a circle and throw a ball to each other. First girl holding a ball throws it to the K-th girl on her left (1 ≤ K ≤ N/2). That girl catches the ball and in turn throws it to the K-th girl on her left, and so on. So the ball is passed from one girl to another until it comes back to the first girl. If for example N = 7 and K = 3, the girls receive the ball in the following order: 1, 4, 7, 3, 6, 2, 5, 1.
To make the game even more interesting the girls want to choose K as large as possible, but they want one condition to hold: each girl must own the ball during the game.
Input
Input contains one integer number N (3 ≤ N ≤ 10 2000) — the number of Chinese girls taking part in the game.
Output
Output the only number — K that they should choose.
Sample Input
7
6
Sample Output
3
1
题意：给定一个很大的数N，求一个数K，K大于等于1小于等于N/2，使得gcd(N,K)=1。
题解：打表可以发现规律。
打表可以发现规律 奇数就是除以2 偶数如果是4的倍数则除以2减1 偶数如果非4的倍数则除以2减2
接下来就是代码的实现了，用字符串存储数组。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int main()
{
int a[],b[];
char c[];
while(scanf("%s",c)!=EOF)
{
memset(a,,sizeof(a));
memset(b,,sizeof(b));
int len=strlen(c);
int cnt=;
for(int i=; i<len; i++)
a[i]=c[i]-'';
for(int i=; i<len; i++)
{
b[i]=(a[i]+cnt*)/;
if(a[i]%==)
cnt=;
else
cnt=;
}
int jian=;
int sum=a[len-]*+a[len-];
//奇数就是除以2 偶数4的倍数除以2减1 偶数非4的倍数除以2减2
if(sum%==)
{
if(sum%==)
jian=;
else
jian=;
}
int sumb=,k=;
if(jian==)
{
int flag1=;
for(int i=len-; i>=; i--)
{
if(b[i]==)
{
flag1=;
continue;
}
else
{
k=i;
for(int j=k;j<len-;j++)
b[j]--;
if(flag1)
b[len-]=;
else
b[len-]--;
break;
}
}
}
else if(jian==) //
{
int flag=;
int flag2=;
if(b[len-]>=) //这个和上面的len-1不一样
{
b[len-]-=;
flag=;
flag2=;
}
for(int i=len-; i>=; i--) //最后一位肯定不行的
{
if(flag)
break;
if(b[i]==)
{
flag2=;
continue;
}
else
{//
k=i;
for(int j=k;j<len-;j++)
b[j]--;
b[len-]=b[len-]+-;
break;
}
}
}
int j=;
while(b[j]==) j++;
for(; j<len; j++)
printf("%d",b[j]);
printf("\n");
} return ;
}