算法分析

是否存在a,b,c，使得a，b，c既是一个等差数列，也是一个等比数列
证明：

• 若a,b,c是一个等差数列，因此a + c = 2b(1)
• 若a,b,c是一个等比数列，因此(2)a * c = b^2(2)
• 对(2)乘上4,得到4 * a * c = 4 * b^2(3)
• 对(1)两边加平方，得到(a + c)^2 = 4 * b^2(4)
• 联立(3)，(4)可得(a - c)^2 = 0，即a = c = b

因此当且仅当a == b == c时，它既是一个公差为0的等差数列也是一个公比为1的等比数列，因此它的第k项用等差数列和等比数列求出来的结果是一样的

两种情况

• 情况1：若a,b,c是一个等差数列，则第k项是a + (c - b) * (k - 1)
• 情况2：若a,b,c是一个等比数列，则第k项是a * (b / c)^(k - 1)，其中b / c一定是一个整数，用快速幂求解

时间复杂度 $O(logn)$

参考文献

算法提高课

Java 代码

import java.util.Scanner;

public class Main {
    static int mod = 200907;
    static long qmi(int a,int k)
    {
        long res = 1 % mod;
        long t = a;
        while(k > 0)
        {
            if((k & 1) != 0) res = res * t % mod;
            k >>= 1;
            t = t * t % mod;
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while(T -- > 0)
        {
            int a = scan.nextInt();
            int b = scan.nextInt();
            int c = scan.nextInt(); 
            int k = scan.nextInt();
            if(a + c == 2 * b) System.out.println((a + (long)(c - b) * (k - 1)) % mod);
            else System.out.println(a * qmi(c / b,k - 1) % mod);
        }
    }
}