题解 P16345 阿瓦的数列

zsz_qaq · 2026-04-22 21:44:46 · 题解

前言

抢个第一。（后记：失败了）

分析

显然，对于每组数据，我们的时间复杂度不应该超过 O(1)，不然有可能会 TLE。
通过分析发现，当数列中出现 0 时，后面的所有项都是 0，且当 i 超过一定值后，数列会稳定或出现 0。因此，只需计算前 100 项左右即可。

代码实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        long long x, y, n;
        cin >> x >> y >> n;
        if (n == 1) {
            cout << x << endl;
            continue;
        }
        if (n == 2) {
            cout << y << endl;
            continue;
        }
        if (x == 0 || y == 0) {
            cout << 0 << endl;
            continue;
        }
        long long a = x, b = y;
        bool f = 0;
        for (long long i = 3; i <= n && i <= 100; ++i) {
            __int128 c = b * a % i;
            if (c == 0) {
                f = 1;
                break;
            }
            a = b;
            b = c;
            if (i == n) {
                break;
            }
        }
        if (f) {
            cout << 0 << endl;
        } else {
            cout << b << endl;
        }
    }
    return 0;
}