2981920_tle.cpp

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

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

void divide(char tmp[], int n)
{
	int l, i, t, s, mark;
	char q[10011];

	l = strlen(tmp);
	i = t = 0;
	mark = 1;
	while(1&&mark)
	{	
		while(t<n&&i<l)
		{
	     	t *= 10;
	     	t += tmp[i]-'0';
			q[i] = '0';
			i++;
		}
		s = t / n;
		if(!s)
			mark = 0;
		if(mark)
			q[i-1] = s+'0';
		t -= s*n;
	}
	q[i] = '\0';
	for(i = 0; q[i] != '\0'; i++)
		if(q[i]!='0')
		{
			strcpy(q,&q[i]);
    		break;
		}
	strcpy(tmp,q);
}

char num[10011];

void add(char a[],char b[])
{
	int i, l, w, t;
	int l1, l2;

	l1 = strlen(a);
	l2 = strlen(b);
	l = l1>l2?l1:l2;
	w = 0;
	for(i = 0; i < l; i++)
	{
		if(i>=l1)
			a[i] = '0';
		if(i>=l2)
			b[i] = '0';
		t = a[i]+b[i]-'0'-'0'+w;
		if(t>=10)
			t%=10,w=1;
		else
			w = 0;
		a[i] = t + '0';
	}
	if(w)
		a[i++] = '1';
	a[i] = '\0';
}

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

	l= strlen(temp);
	lT = strlen(Tmp);
	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 main()
{
	int l;
	char ans[10011];

	scanf("%s",num);
	strcpy(ans,"1");
	while(num[0]!='0')
	{
		l = strlen(num);
		if((num[l-1]-'0')%2==1)
		{
			add(ans,ans);
		}
		divide(num,2);
	}
	minus(ans,"1");
	puts(ans);
	return 0;
}