2219 - 数列3

小明有天在做数学题，碰到这样一个问题，只告诉你一个数列的前三个数，并且这个数列一定是等差数列或等比数列中的一种，问你这个数列的第k个数是什么。现在请你编程帮小明解答这个问题。

题目输入

输入的第一行是一个整数n，表示共有n组数列。
接下来n行，每行输入四个整数，前三个数表示数列的前三个数，第四个数就是题目描述中的k。
其中0<k<=10^9，其他三个数的范围为[0,2^63)。题目保证输入的数列为非降序的。

题目输出

对于每组数列，输出数列中的第k个数模（%）200907后的结果。

输入/输出样例

题目输入

2
1 2 3 5
1 2 4 5

题目输出

5
16

C语言解答

#include <stdio.h>
#define MOD 200907

long long g(long long q, long long k) {
    long long sum = 1, a[1000], i = 0;
    while (k) {
        if (k % 2 != 0)
            a[i++] = 1;
        else
            a[i++] = 0;
        k /= 2;
    }
    i--;
    for (i; i >= 0; i--) {
        sum = (sum * sum) % MOD;
        if (a[i])
            sum = (sum * q) % MOD;
    }
    return sum % MOD;
}


int main() {
    long long a, b, c, k, t, d, q;
    int n;
    scanf("%d", &n);
    while (n--) {
        scanf("%lld%lld%lld%lld", &a, &b, &c, &k);
        if (b - a == c - b) {
            d = b - a;
            t = ((((k - 1) % MOD) * (d % MOD)) % MOD + a % MOD) % MOD;
            printf("%lld\n", t);
        } else {
            q = b / a;
            printf("%lld\n", (a % MOD * g(q, k - 1)) % MOD);
        }
    }
    return 0;
}

C++解答

#include <stdio.h>
#define MOD 200907

long long g(long long q, long long k) {
	long long sum = 1, a[1000], i = 0;
	while (k) {
		if (k % 2 != 0)
			a[i++] = 1;
		else
			a[i++] = 0;
		k /= 2;
	}
	i--;
	for (i; i >= 0; i--) {
		sum = (sum * sum) % MOD;
		if (a[i])
			sum = (sum * q) % MOD;
	}
	return sum % MOD;
}
int main() {
	long long a, b, c, k, t, d, q;
	int n;
	scanf("%d", &n);
	while (n--) {
		scanf("%lld%lld%lld%lld", &a, &b, &c, &k);
		if (b - a == c - b) {
			d = b - a;
			t = ((((k - 1) % MOD) * (d % MOD)) % MOD + a % MOD) % MOD;
			printf("%lld\n", t);
		} else {
			q = b / a;
			printf("%lld\n", (a % MOD * g(q, k - 1)) % MOD);
		}
	}
	return 0;
}

时间限制	1 秒
内存限制	32 MB

讨论统计

上一题下一题