무한 서열

D e s c r i p t i o n Description Description

우리는 다음과 같은 방식으로 서열을 생성한다. 1. 시작할 때 서열은'1'이다.2. 매번 변화는 서열의 "1"을 "10", "0"을 "1"으로 만든다.무한한 변화를 거쳐 우리는 서열'10101010101010101101...'을 얻었다.총 Q 개의 질문이 있는데, 매번 질문은 구간 A와 B 사이에 몇 개의 1이 있는지 하는 것이다.퀘스트는 Q개의 질문에 대답하는 프로그램을 작성합니다

I n p u t Input Input

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

O u t p u t Output Output

총 Q 행, 각 행마다 응답

S a m p l e Sample Sample I n p u t Input Input

1
2 8

S a m p l e Sample Sample O u t p u t Output Output

H i n t Hint Hint

1 <= Q <= 5000 1 <= a <= b < 2^63

T r a i n Train Train o f of of T h o u g h t Thought Thought

먼저 그 서열을 보면 피보나치 수열의 형식에 따라 점차적으로 증가하는 것을 발견할 수 있다. 그리고 우리는 접두사와 발견을 추가할 수 있다.

C o d e Code Code

#include
#include
using namespace std;
long long f[1005][2],Q; long long a,b;
long long work(long long x)
{
	if (x==0) return 0;
	for (int i=0; i<=100; ++i)
	{
		if (x==f[i][1]) return f[i][0];// 
		 else if (x<f[i][1]) return f[i-1][0]+work(x-f[i-1][1]);// 
	}
}
int main()
{
	scanf("%lld",&Q);
	f[0][0]=1; f[0][1]=1;//f[0][0] 1 
	f[1][0]=1; f[1][1]=2;//f[0][1] 
	for (int i=2; i<=100; ++i)
	  f[i][0]=f[i-1][0]+f[i-2][0],f[i][1]=f[i-1][1]+f[i-2][1];
	for (int i=1; i<=Q; ++i)
	{
		scanf("%lld%lld",&a,&b);
		printf("%lld
",work(b)-work(a-1));
	}
	return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

백준10870

오늘부터 하나씩 풀어보는 알고리즘 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 F...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다