题目地址:

http://codeforces.com/gym/100199/attachments/download/1686/20022003-winter-petrozavodsk-camp-andrew-stankevich-contest-1-en.pdf

题目大意:

有n个人在传球

每个人会把球丢给她左边第k个人,因为k>n/2就没有意义了所以1<=k<=n/2

求最大的k,满足从1号开始n次,每个人都能拿到球并且回到1号

这是个数学题

如果n是奇数,那么答案是n/2

证明如下:

这是显然的,为什么要证明?

我们可以把问题等价于求最大的k使得gcd(n,k)=1

什么这个也要证?

实际上这个的证明比较神奇

我们来证明gcd(n,k)=1 --> k是合法解

假设存在a,b,使得ak%n=bk%n,a!=b(mod n)

那么ak=bk(mod n),gcd(n,k)=1 ==> a=b(mod n)

矛盾,X(PS:上述有的=实际上是三横)

我们来证明k是合法解 --> gcd(n,k)=1

假设k是合法解,gcd(n,k)!=1

那么存在t=n/gcd(n,k)

t<n,走过t次以后在0号位置,而n次以后也在0号位置

冲突,X

那么下面就要证明gcd(n/2,n)=1了

gcd(n/2*2,n)=gcd(n-1,n)=1

所以gcd(n/2,n)=1

如果n是偶数呢?

如果n/2是偶数,答案是n/2-1

如果n/2是奇数,答案是n/2-2 (n=2除外,此时答案是1,不过数据保证n>=3)

首先,n=2^a₀*p₁^a₁*p₂^a₂...

然后我们不管和2的gcd,只看和p₁^a₁...p_n^a_n的gcd

因为除了2以外,p>=3,所以

gcd(n/2-1,n/2)=1

gcd(n/2-2,n/2)=1(n/2是奇数)

在n/2是偶数的时候,gcd(n/2-1,n/2)=1,n/2-1是奇数,所以gcd(n/2-1,n)=1

在n/2是奇数的时候,gcd(n/2-2,n/2)=1,n/2-2是奇数,所以gcd(n/2-1,n)=1

没了

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char a[4005];
int b[4005];
int c[4005];
int main()
{
    freopen("china.in","r",stdin);
    freopen("china.out","w",stdout);
    scanf("%s",a);
    int i;
    int n=strlen(a);
    for (i=0;i<n;i++)
    {
        b[i]=a[i]-'0';
    }
    int sum=0;
    for (i=0;i<n;i++)
    {
        sum*=10;
        sum+=b[i];
        c[i]=sum/2;
        sum%=2;
    }
    if (sum==1)
    {
        for (i=0;i<n-1;i++)
        {
            if (c[i]!=0) break;
        }
        for (;i<n;i++)
        {
            printf("%d",c[i]);
        }
        puts("");
        return 0;
    }
    if (c[n-1]%2==0)
    {
        c[n-1]--;
    }
    else
    {
        c[n-1]-=2;
    }
    int t=n-1;
    for (;t>=0;)
    {
        if (c[t]<0)
        {
            c[t]+=10;
            c[t-1]--;
            t--;
        }
        else
        {
            break;
        }
    }
    for (i=0;i<n-1;i++)
    {
        if (c[i]!=0) break;
    }
    for (;i<n;i++)
    {
        printf("%d",c[i]);
    }
    puts("");
    return 0;
}