2745174_ac_62ms_284k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char ans[500];
int no;
typedef struct node
{
	char ans[500];
}Num;

void minus(char temp[],char Tmp[])
{
    int i, l, lT, w, tmp;
    char ch;

    l= strlen(temp);
    lT = strlen(Tmp);
    for(i = 0; i < l/2; i++)
    {
        ch = temp[i];
        temp[i] = temp[l-i-1];
        temp[l-i-1] = ch;
    }
    if(strcmp(temp,Tmp)==0)
    {
        strcpy(temp,"0");
        return ;
    }
    w = 0;
    for(i = 0; i < l; i++)
    {
        if(i < lT)
            ch = Tmp[i];
        else
            ch = '0';
        tmp = (temp[i]-'0')-(ch-'0')-w;
        if(tmp<0)
        {
            w = 1;
            tmp += 10;
        }
        else
            w = 0;
        temp[i] = '0'+tmp;
    }
    for(i = l-1; i >= 0; i--)
        if(temp[i]!='0')
        {
            temp[i+1] = '\0';
            break;
        }
    l = strlen(temp);
    for(i = 0; i < l/2; i++)
    {
        ch = temp[i];
        temp[i] = temp[l-i-1];
        temp[l-i-1] = ch;
    }
}

int cmp(char tmp[],char t2[])
{
    if(strlen(tmp)<strlen(t2)||(strlen(tmp)==strlen(t2)&&strcmp(t2,tmp)>=0))
        return 1;
    return 0;
}

int zero(char str[])
{
    int i;
        
    for (i = 0; str[i]!='\0'; i++)
    {
        if(str[i]!='0')
            return 0;
    }
    return 1;
}

void reserve(char tmp[])
{
    int i, l;
    char ch;

    l = strlen(tmp);
    for(i = 0; i < l/2; i++)
    {
        ch = tmp[i];
        tmp[i] = tmp[l-i-1];
        tmp[l-i-1] = ch;
    }
}

void divide(char num[],char r[])
{
    int i;
    char tt[500];

    while (no<50)
    {
        i = 0;
        strcpy(tt,r);
        reserve(tt);
        if (cmp(r,num))
        {
            while (cmp(r,num))
            {
                i++;
                minus(num,tt);
            }
            ans[no++] = i+'0';
            if (!zero(num))
            {
                strcat(num,"0");
            }
            else
                return ;
        }
        else
        {
            ans[no++] = '0';
            strcat(num,"0");
        }
    }
}

void Muti(char Tmp[],char t1[])
{
    int tmp, w, p;
    char ans[500];
    int l1, l2, i, j;

    l1 = strlen(Tmp);
    l2 = strlen(t1);
    p = 1;
    for(i = 0; i < 400; i++)
        ans[i] = '0';
    for(i = 0; i < l2; i++)
    {
        w = 0;
        for(j = 0; j < l1; j++)
        {
            tmp = (Tmp[j]-'0')*(t1[i]-'0')+w;
            tmp += ans[j+i]-'0';
            ans[j+i] = tmp%10+'0';
            w = tmp/10;
        }
        if(w)
            ans[j+i] = '0'+w;
    }
    if(w)
        p = 0;
    ans[j+i-p] = '\0';
    strcpy(Tmp,ans);
}

Num muti(Num a,Num b)
{
	char tmp[500];

	strcpy(tmp,a.ans);
	reserve(tmp);
	reserve(b.ans);
	Muti(tmp,b.ans);
	reserve(tmp);
	if (strlen(tmp)>50)
		tmp[50] = '\0';
	strcpy(a.ans,tmp);
	return a;
}

Num cal(Num a,__int64 n)
{
	if(n == 1)
		return a;
	if(n % 2)
		return muti(cal(a,n-1),a);
	else
	{
		Num tmp = cal(a,n/2);
		return muti(tmp,tmp);
	}
}

int main()
{
	char num[500], nn[500], mm[500];
	__int64 n;
	int len, i;
	Num a;

	while(scanf("%s",num)==1)
	{
		if(num[0]=='0')
			break;
		strcpy(nn,num);
		strcpy(mm,num);
		minus(nn,"1");
		minus(mm,"2");
		strcat(nn,"0");
		no = 0;
		divide(nn,num);
		ans[no] = '\0';
		n = _atoi64(mm);
		strcpy(a.ans,ans);
		a = cal(a,n);
		len = strlen(a.ans);
		if (len>14)
			a.ans[14] = '\0', len = 14;
		printf("0.%s",a.ans);
		for(i = len; i < 14; i++)
			printf("0");
		printf("\n");
	}
	return 0;
}