178.c

来自「平时acm训练时ac的源代码」· C语言 代码 · 共 57 行

/*
178. Golden chain 
 Accepted 66 ms 114 kb 
*/

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

int main()
{
	int w, i;
	long N[2]={0,0}, j=1;
	char in[20];

	long a1, a0;
	long q[2]={0,4};

	scanf("%s", in);
	w = strlen(in);
	if (1==w && in[0]=='1')
	{
		printf("0");
	}
	else
	{
		for (i=w-1; i>=0 && i>=w-7; i--)
		{
			N[1] += (in[i]-48)*j;
			j *=10;
		}
		for (j=1; i>=0; i--)
		{
			N[0] += (in[i]-48)*j;
			j *=10;
		}
		for (i=2; 1; i++)
		{
			a0 = q[0]*i;
			a0 += (q[1]*i)/10000000;
			a1 = (q[1]*i)%10000000;
			if (N[0]<a0 || (N[0]==a0 && N[1]<a1))
			{
				break;
			}
			q[0] *= 2;
			q[1] *= 2;
			if (q[1]>999999)
			{
				q[0] += q[1]/10000000;
				q[1] = q[1]%10000000;
			}
		}
		printf("%d",i-1);
	}
}