무한 시퀀스【시뮬레이션】

SSLOJ 1343 무제한 시퀀스

Description--

Input--

Output--

Sample Input--

Sample Output--

4

설명 -- 4

4

문제 풀이 방향 -- 4

4

코드 -- 4

Description–

우리는 다음과 같은 방식으로 서열을 생성한다. 1. 시작할 때 서열은'1'이다.2. 매번의 변화는 서열 중의'1'을'10','0'을'1'으로 바꾼다.무한한 변화를 거쳐 우리는 서열'1010101101010101101...'을 얻었다.모두 Q개의 질문이 있는데 매번 질문은 다음과 같다. 구간 A와 B 사이에 1이 몇 개 있느냐.퀘스트는 프로그램을 써서 Q개의 질문에 대답합니다

Input–

첫 번째 행위는 하나의 정수 Q이다. 뒤에 Q 줄이 있고 줄마다 두 개의 수는 빈칸으로 구분된 정수 a, b이다.

Output–

총 Q행, 각 행마다 응답

Sample Input–

1 2 8

Sample Output–

4

설명 –

1 <= Q <= 5000 1 <= a <= b < 263

문제풀이 사고 –

i번째=i-1개+i-2개 그리고 1~b의 1의 개수로 1~a의 1의 개수를 빼면 ok(구체적으로 코드 참조)

코드 –

#include
#include
using namespace std;
long long q,x,y,by,a[100],b[100];
long long fy(long long ll)
{
	for (int i=1;i<=92;++i)
	{
		if (b[i]==ll) return a[i];
		if (b[i]>ll) return a[i-1]+fy(ll-b[i-1]);//    
	}
} 
int main()
{
	a[1]=a[2]=b[1]=1,b[2]=2;
	for (int i=3;i<=92;++i)
	  a[i]=a[i-2]+a[i-1],b[i]=b[i-2]+b[i-1];//  
	scanf("%lld",&q);
	for (int i=1;i<=q;++i)
	{
		scanf("%lld%lld",&x,&y);
		by=fy(y);
		if (x==1) printf("%lld
",by);
		else printf("%lld
",by-fy(x-1));//"b-a"
	}
	
	return 0;
}