QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#631089#5301. Modulo Ruins the LegendwdwWA 0ms3540kbC++201.8kb2024-10-11 21:57:342024-10-11 21:57:34

Judging History

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

  • [2024-10-11 21:57:34]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3540kb
  • [2024-10-11 21:57:34]
  • 提交

answer

#include<bits/stdc++.h>

#define int long long
using namespace std;
using ll = long long;
using ld = double;
const ll mod = 1e9 + 7;
const ll inf = 1e9;
const int N = 2e5 + 10;

int x, y;
//ax+by=c
//裴蜀定理得c%gcd(a,b)==0才有解 解ax=c(mod b)=ax+by=c 可解得x=x0*c/gcd(a,b),此时mod(b(b值会变化)/gcd(a,b))
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int x1, y1;
    int d = exgcd(b, a % b, x1, y1);
    x = y1, y = x1 - a / b * y1;
    return d;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a1(n + 5);
    int w1 = gcd(n, n * (n + 1) / 2);
    int w2 = gcd(w1, m);
    int ans = 0;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a1[i];
        ans += a1[i];
        ans %= w2;
        sum += a1[i];
    }
    cout << ans << '\n';
    int k2 = -(sum - ans) / w2;
    int a = w1, b = m;
    x = 0, y = 0;
    int d = exgcd(a, b, x, y);
    int l = b / d;
    x *= k2 % l;
    x %= l;
    x += l;
    x %= l;
    //  x+=l;
    int k1 = x;
    a = n, b = (n) * (n + 1) / 2;
    x = 0, y = 0;
    d = exgcd(a, b, x, y);
    l = b / d;
    int l1 = a / d;
    x *= k1 % l;
    y *= k1 % l1;
    if (x < 0) {
        int w1 = abs(x / l);
        x += w1 * l;
        y -= w1 * l1;
        if (x < 0) {
            x += l;
            y -= l1;
        }
    }
    // cout << x << " " << y << '\n';
    if (y < 0) {
        x -= l;
        y += l1;
    }
    if (x < 0) {
        x += m;
    }
    cout << x << " " << y << '\n';

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//    cout<<fixed<<setprecision(2);
//    srand(time(0));
    int T = 1;
    // cin >> T;
    while (T--)solve();
    return 0;
}

詳細信息

Test #1:

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

input:

6 24
1 1 4 5 1 4

output:

1
22 -1

result:

wrong answer Integer parameter [name=d] equals to -1, violates the range [0, 23]