QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#631089 | #5301. Modulo Ruins the Legend | wdw | WA | 0ms | 3540kb | C++20 | 1.8kb | 2024-10-11 21:57:34 | 2024-10-11 21:57:34 |
Judging History
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]