VJudge--A sequence of numbers

题目 - A sequence of numbers

Xinlv wrote some sequences on the paper a long time ago, they might be arithmetic or geometric sequences. The numbers are not very clear now, and only the first three numbers of each sequence are recognizable. Xinlv wants to know some numbers in these sequences, and he needs your help.

Input

The first line contains an integer N, indicting that there are N sequences. Each of the following N lines contain four integers. The first three indicating the first three numbers of the sequence, and the last one is K, indicating that we want to know the K-th numbers of the sequence.

You can assume 0 < K <= 10^9, and the other three numbers are in the range [0, 2^63). All the numbers of the sequences are integers. And the sequences are non-decreasing.

Output

Output one line for each test case, that is, the K-th number module (%) 200907.

Sample Input

2
1 2 3 5
1 2 4 5

Sample Output

5
16

题目大意:

现在有一个由整数组成的序列，可能是等差数列，也可能是等比数列，但是只给出前3个数，要求你求数列中第k个数% 200907的结果。所给数列是一个非递减数列。

输入：首先是一个t表示输入的实例个数，以下t行每行代表一个实例。每行包括4个整数，前3个整数在[0, 2^63)范围内，表示数列的头3个数，第4个数是k表示要求的数列中的第k个数。其中0 < k <= 10^9。

输出：输出数列中第k个数%200907的结果。

思路：

需要用到快速幂算法，注意一下使用long long型。

AC代码：

#include<iostream>
using namespace std;

const int N = 200907;
typedef long long ll;

ll fun(ll a, ll b, ll k) {
	ll base = b / a;
	ll res = 1;
	while(k) {
		if(k & 1) 
			res = (res * base) % N;
		base = (base * base) % N;
		k >>= 1;
	}
	return res;
}

int main() {
	ll a, b, c, k, res;
	int t; 
	scanf("%d", &t);
	for(int i = 0; i < t; ++i) {
		scanf("%I64d%I64d%I64d%I64d", &a, &b, &c, &k);
		if(a + c == 2 * b)
			res = (a+(k - 1)*(b - a)) % N;
		else 
			res = a * fun(a, b, k - 1) % N;
		printf("%I64d\n", res);	
	} 
	return 0;
}