QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#794912#9799. Magical Paletteucup-team3584#WA 51ms12556kbC++232.4kb2024-11-30 16:48:562024-11-30 16:48:57

Judging History

你现在查看的是最新测评结果

  • [2024-11-30 16:48:57]
  • 评测
  • 测评结果:WA
  • 用时:51ms
  • 内存:12556kb
  • [2024-11-30 16:48:56]
  • 提交

answer

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

typedef long long ll;

// Function to compute extended GCD
ll extended_gcd_func(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll g = extended_gcd_func(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// Function to compute inverse of a modulo m
ll mod_inverse(ll a, ll m) {
    ll x, y;
    ll g = extended_gcd_func(a, m, x, y);
    if (g != 1) {
        return -1; // inverse doesn't exist
    } else {
        ll res = (x % m + m) % m;
        return res;
    }
}

void slv() {
    ll n, m;
    cin >> n >> m;
    ll N = n * m;
    // Check gcd(n,m)==1
    ll g = gcd(m, n);
    if (g != 1) {
        cout << "No\n";
        return;
    }

    // 構築方法の修正
    // 数列 A を a_i = 1 + i * m として構築
    vector<ll> A;
    for (ll i = 0; i < n; i++) {
        ll val = 1 + i * m;
        // モジュロ N で調整(必要に応じて)
        if (val > N) val -= N;
        A.push_back(val);
    }

    // 数列 B を b_j = 1 + j * n として構築
    vector<ll> B;
    for (ll j = 0; j < m; j++) {
        ll val = 1 + j * n;
        // モジュロ N で調整(必要に応じて)
        if (val > N) val -= N;
        B.push_back(val);
    }

    // 生成されたすべての (a_i * b_j) % N がユニークであることを確認
    vector<bool> used(N, false);
    bool valid = true;
    for (auto a_val : A) {
        for (auto b_val : B) {
            ll res = (a_val * b_val) % N;
            if (used[res]) {
                valid = false;
                break;
            }
            used[res] = true;
        }
        if (!valid) {
            break;
        }
    }

    if (!valid) {
        // 万が一重複が発生した場合(理論的には発生しないはず)
        cout << "No\n";
        return;
    }

    // 数列 A を出力
    cout << "Yes\n";
    for (int i = 0; i < A.size(); i++) {
        if (i > 0) cout << " ";
        cout << A[i];
    }
    cout << "\n";

    // 数列 B を出力
    for (int i = 0; i < B.size(); i++) {
        if (i > 0) cout << " ";
        cout << B[i];
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    while (q--) {
        slv();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3596kb

input:

2
2 3
2 2

output:

Yes
1 4
1 3 5
No

result:

ok 2 cases (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 51ms
memory: 12556kb

input:

1
1 1000000

output:

Yes
1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

result:

wrong answer Integer parameter [name=b[1000000]] equals to 1000000, violates the range [0, 999999] (test case 1)