51Nod - 알고리즘 말 라 송 13 - C - 크기

두 개의 수열 A 와 B 가 이미 알 고 있 는 A0,a,b,N A_n=A_(n - 1) * a + b (n > = 1) B 수열 만족 Bn=2*B_(n / 2) + 1 (n 은 짝수) Bn=2*B_(n - 1) / 2) + (n + 1) / 2 (n 은 홀수)
지금 B 수열 의 A 에 게 물 어보 세 요.N 항 과 제 (A N) + 1 항의 관계
T 조 데이터 A0, a, b, N < = 1e15 T < = 100 Input 1 개 수 T, 데이터 그룹 수 줄 당 4 개 수 A0, a, b, N Output 한 글자 로 크기 관 계 를 표시 합 니 다.입력 예제 1 0 55 1 출력 예제 =
이 문 제 는 두 가지 어 려 운 점 이 존재 한다. 첫 번 째 는 B 서열 을 어떻게 구 하 느 냐 하 는 것 이다. 두 번 째 는 A 서열 이다. 이 두 가지 서열 은 모두 너무 방대 하 다. 먼저 B 서열 을 말 하면 이것 은 상대 적 으로 간단 하 다. 왜냐하면 B 서열 은 고정 적 인 것 이기 때문이다. B [0] = - 1, 그 다음 에 고정된 서열 이다. 뚜렷 하 다. 앞의 네 개 는 특수 하고 뒤의 네 개 는 모두 네 개의 크기 규칙 에 부합 되 기 때문이다.여기 서 우 리 는 A 서열 을 다시 말 해 야 한다. 비록 A 서열 에 고정된 값 이 없 지만 A 서열 은 통식 이 존재 하고 뒤에 등비 관계 가 존재 하 며 앞 에 똑 같이 특수 한 상황 이 존재 하기 때문에 특별히 고려 해 야 한다. 계산 에서 나머지 를 취하 면 된다.
코드 C 는 다음 과 같 습 니 다:

#include <stdio.h>

typedef long long ll;

ll a, b, N;
ll A_0, A_N, A;

ll setA(ll N)
{
    A = A_0 % 4;
    for (int i = 1; i <= N; i++)
    {
        A = (A * a + b) % 4;
    }
    return A;
}

int main(int argc, const char * argv[])
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%lld %lld %lld %lld", &A_0, &a, &b, &N);
        int flag = 1;
        ll lim = 4, A = A_0;
        flag = ((b <= lim) && (A <= lim));

        for (int i = 1; i <= N && flag; i++, A = A * a + b)
        {
            flag = (A < (lim - b) * 1.0 / a);
        }
        if (flag)
        {
            puts(A == 0 || A == 1 ? "=" : A == 2 ? "<" : ">");
            continue;
        }

        A = setA(N > 3 ? N % 4 + 4 : N);

        puts(A == 1 ? "=" : A == 3 ? ">" : "<");

    }
    return 0;
}