QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#794888#9799. Magical Paletteucup-team3584#WA 0ms3584kbC++232.3kb2024-11-30 16:41:132024-11-30 16:41:16

Judging History

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

  • [2024-11-30 16:41:16]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3584kb
  • [2024-11-30 16:41:13]
  • 提交

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;
    }
}

// Function to check if N is square-free
bool is_square_free(ll N) {
    if (N == 1) return true;
    for (ll p = 2; p * p <= N; p++) {
        if (N % p == 0) {
            if ((N / p) % p == 0) {
                return false;
            }
            while (N % p == 0) {
                N /= p;
            }
        }
    }
    if (N > 1) return true;
    return true;
}

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;
    }

    vector<ll> A;
    for (ll i = 0; i < n; i++)
        A.push_back(1 + 2 * i);

    // 数列 B を適切にスケーリング
    // b_j = (offset + j * step) mod N でユニークにする
    // step を n の逆元に設定
    ll n_inv = mod_inverse(n, m);
    if (n_inv == -1) {
        // 理論的には gcd(n, m) ==1 であるため、逆元は必ず存在する
        cout << "No\n";
        return;
    }

    // 任意のオフセット(ここでは1)を選択
    ll offset = 1;
    vector<ll> B;
    for (ll j = 0; j < m; j++) {
        ll val = (offset + j * n_inv * n) % N;
        if (val == 0) val = N;
        B.push_back(val);
    }

    cout << "Yes"
         << "\n";
    // Output A
    for (int i = 0; i < A.size(); i++) {
        if (i > 0) cout << " ";
        cout << A[i];
    }
    cout << "\n";
    // Output B
    for (int i = 0; i < B.size(); i++) {
        if (i > 0) cout << " ";
        cout << B[i];
    }
    cout << "\n";
}

int main() {
    int q;
    cin >> q;
    while (q--) {
        slv();
    }
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3584kb

input:

2
2 3
2 2

output:

Yes
1 3
1 5 3
No

result:

wrong answer Duplicated Color 3 (test case 1)