题解：P13460 [GCJ 2008 #1B] Crop Triangles

__coderyc__ · 2025-07-30 23:14:52 · 题解

思路

烤鸡既视感。

对于每一个可能的点的三元组进行枚举，如果符合题目中这三个点行坐标和与列坐标和除以三都是整数，计入答案，不就六层循环而已。

这里有个小技巧，如果除以三是整数，说明这个数除以三的余数是零，不必硬要算出这个数除完是几。

注意题目中提到的生成树坐标的方式及 GCJ 标准格式化输出就行啦。

代码

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

int main() {
    int N;
    cin >> N;
    for (int c = 1; c <= N; ++c) {
        int n, A, B, C, D, x0, y0, M;
        cin >> n >> A >> B >> C >> D >> x0 >> y0 >> M;
        int cnt[3][3] = {0};
        long long X = x0, Y = y0;
        cnt[X % 3][Y % 3]++;
        //数据生成器
        for (int i = 1; i < n; ++i) {
            X = (A * X + B) % M;
            Y = (C * Y + D) % M;
            cnt[X % 3][Y % 3]++;
        }
        long long ans = 0;  //十年OI一场空，_______
        for (int a = 0; a < 3; ++a) {  //第一点x
            for (int b = 0; b < 3; ++b) { //第一点y
                for (int c = 0; c < 3; ++c) { //第二点x
                    for (int d = 0; d < 3; ++d) {
                        for (int e = 0; e < 3; ++e) { //第二点y，后面就是第三个点的x和y
                            for (int f = 0; f < 3; ++f) {
                                if ((a + c + e) % 3 == 0 && (b + d + f) % 3 == 0) {
                                    long long cnt1 = cnt[a][b];
                                    long long cnt2 = cnt[c][d];
                                    long long cnt3 = cnt[e][f];
                                    if (a == c && b == d) cnt2--;
                                    if (a == e && b == f) cnt3--;
                                    if (c == e && d == f) cnt3--;
                                    if (cnt1 > 0 && cnt2 > 0 && cnt3 > 0) {
                                        ans += cnt1 * cnt2 * cnt3;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        ans /= 6; 
        cout << "Case #" << c << ": " << ans << endl; //格式化输出
    }
    return 0;
}

抢个最优解。