51Nod－算法马拉松13－C－比大小

有两个数列A和B
已知A_0,a,b,N
A_n=A_(n-1)*a+b (n>=1)
B数列满足
B_n=2*B_(n/2) + 1 (n为偶数)
B_n=2*B_((n-1)/2) + (n+1)/2 (n为奇数)

现在问B数列的第A_N项和第(A_N)+1项的关系

T组数据
A_0,a,b,N<=1e15
T<=100
Input
一个数T，数据组数
每行四个数A_0,a,b,N
Output
一个字符，表示大小关系。
Input示例
1
0 5 5 1
Output示例
＝

这道题，存在两处难点，第一就是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;
}