acdream 1210 Chinese Girls' Amusement (打表找规律)

题意：有n个女孩围成一个圈从第1号女孩开始有一个球，可以往编号大的抛去（像传绣球一样绕着环来传），每次必须抛给左边第k个人，比如1号会抛给1+k号女孩。给出女孩的人数，如果他们都每个人都想要碰到球一次，那么这个k应该是多少（满足 1 ≤ K ≤ N/2 且 k必须尽量大）？   例如：n=7，那么1号开始拿球，抛球的顺序是 1, 4, 7, 3, 6, 2, 5, 1.  当球重新回到1女孩手中时，每个人刚好只玩了一次。注：这个数字相当大(3 ≤ N ≤ 10²⁰⁰⁰) 

思路：

方法（1）：

暴力本地打表，发现n为奇数时，k=(n-1)/2即可。n为偶数时，规律如下图（左列是n，右列是k）：

如果n为偶数，且n/2为偶数时，k=(n/2)-1。如果n为偶数，且n/2为奇数时，k=(n/2)-2。需要用到大数的除法和减法。

方法（2）：如果能够经过若干次传球且未开始循环，将球抛到第n个女孩那里去，那么肯定可以全部人玩一次，比如1 2 3 4 5 6 7，应该k=3，第1次传给4号，第2次就到达7号，且还没开始循环。那么7号肯定可以传给3号，因为1号传给4号，7号自然就传给3号，接着球又到了6号那里。接续循环下去，球肯定会重回1号手中，且大家都只玩一次。

那么从n/2开始，逐个递减试，看能不能n模k为1。

// 求模 N%(N/2) != 0 即是结果！
// 奇数：(n-1)/2
// 偶数： n/2 - 1
 
#include <iostream>
#include <cstdio>
#include <string>
 
using namespace std;
 
// 减一操作  strNum 正序存储 如 100000
void subOne(string &strNum)
{
    if (strNum[strNum.length()-1] > '0')
    {
        strNum[strNum.length()-1]--;
        return;
    }
 
    // 可能需要逐位减一
    for(int i=strNum.length()-1; i>=0; --i)
    {
        if (strNum[i] == '0')
        {
            strNum[i] = '9';
        }
        else
        {
            strNum[i]--;
            break;
        }
    }
 
    if (strNum[0] == '0')
        strNum.erase(0, 1); // 移除头位的0
}
 
// strNum / 2
void divHalf(string &strNum)
{
    int s = 0;
    string num;
    for(int i=0; i<strNum.length(); ++i)
    {
        s = s*10 + (strNum[i]-'0');
        num += (s/2 + '0');
        s %= 2;
    }
 
    // 去掉前导0
    int i = 0;
    for(i=0; i<num.length(); ++i)
    {
        if (num[i] != '0')
            break;
    }
    strNum = num.substr(i);
}
 
int main(void)
{
    //freopen("in.txt", "r", stdin);
 
    string strNum;
    while(cin>>strNum)
    {
        // 末位数字判断奇偶性
        int k = strNum[strNum.length()-1]-'0';
        if (k%2==0)
        {
            // 偶数： n/2 - 1
            divHalf(strNum);
            subOne(strNum);
 
            // 这里需要特殊处理
            while(1)
            {
                k = strNum[strNum.length()-1]-'0';
                if (k%2 != 0)
                    break;
 
                subOne(strNum);
            }
        }
        else
        {
            // 奇数：(n-1)/2
            subOne(strNum);
            divHalf(strNum);
        }
        cout<<strNum<<endl;
    }
 
    return 0;
}

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2005;
int a, b;
int has[N];
char s[N];
char ans[N];
 
void div(char * src,int n,char *dest)
{
    int len = strlen(src),i,k,t=0,s=0;
    bool flag = true;    //商是否有了第一个有效位，防止商首部一直出现0
    for(i=0,k=0; i<len; i++)
    {
        t = s*10+(src[i]-48);    //新余数
        if(t/n>0 || t==0)        //余数为0要修改商
        {
            dest[k++] = t/n+48,s = t%n,flag = false;
        }
       else                    //不够除，修改余数
        {
            s = t;
            if(!flag)            //商已经有有效位了，补零
                dest[k++] = '0';
        }
    }
    dest[k]='';
}
 
 
bool comp(string num1,string num2)
{
    int leng=num1.length(),i;
    for(i=0;i<leng;i++){if(num1[i]!='0')break;}
    num1=num1.substr(i,leng);
    if(num1.length()==0)num1="0";
 
    leng=num2.length();
    for(i=0;i<leng;i++){if(num2[i]!='0')break;}
    num2=num2.substr(i,leng);
    if(num2.length()==0)num2="0";
 
    if(num1.length()>num2.length())return true;
    else if(num1.length()==num2.length())
    {
        if(num1>=num2)return true;
        else return false;
    }
    else return false;
}
void _minus(string num1,string num2,string &result)
{
 
    if(comp(num2,num1)){string ss=num1;num1=num2;num2=ss;}
    reverse(num1.begin(),num1.end());
    reverse(num2.begin(),num2.end());
 
    result="";
 
    int i;
    for(i=0;i<int(num1.length())&&i<int(num2.length());i++)
    {
        char c=num1[i]-num2[i]+48;
        result=result+c;
    }
    if(i<int(num1.length()))
        for(;i<int(num1.length());i++)
            result=result+num1[i];
 
    int jiewei=0;
    for(i=0;i<int(result.length());i++)
    {
        int zhi=result[i]-48+jiewei;
        if(zhi<0)   {zhi=zhi+10;jiewei=-1;}
        else    jiewei=0;
        result[i]=(char)(zhi+48);
    }
 
    for(i=result.length()-1;i>=0;i--)
        if(result[i]!='0')
            break;
 
    result=result.substr(0,i+1);
    reverse(result.begin(),result.end());
    if(result.length()==0)result="0";
}
//****上面不用看了，大数模版
 
 
int main()
{
    //freopen("input.txt", "r", stdin);
 
    while(gets(s))
    {
        int len=strlen(s);
        if(((s[len-1]-'0')&1)==1) //奇数
        {
            div(s,2,ans);
            puts(ans);
        }
        else
        {
            div(s,2,ans);   //先减半
            len=strlen(ans);
            if(((ans[len-1]-'0')&1)==0 )    //减半后为偶数
            {
                string tmp(ans);
                string res="";
                _minus(tmp,"1",res);//减1
                cout<<res<<endl;
            }
            else//减半后为奇数
            {
                string tmp(ans);
                string res="";
                _minus(tmp,"2",res);//减2
                cout<<res<<endl;
            }
        }
    } 
    return 0;
}