QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#623849 | #5301. Modulo Ruins the Legend | 2317663977 | WA | 0ms | 3660kb | C++23 | 1.2kb | 2024-10-09 14:12:12 | 2024-10-09 14:12:12 |
Judging History
answer
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <cstring>
using ll = long long;
const int N = 1e5 + 10;
ll n, m;
ll sum;
ll exgcd(ll a, ll b, ll& x, ll& y)
{
if (!b)
{
x = 1;
y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
ll gcd(ll a, ll b)
{
if (a < b) swap(a, b);
return b ? gcd(b, a % b) : a;
}
void solve()
{
cin >> n >> m;
for (int i = 1;i <= n;i++)
{
ll t;
cin >> t;
sum += t;
}
ll y = 0, s = 0;
ll ans1 = sum % gcd(n, m);
ll ans2 = (sum + n * (n + 1) / 2) % gcd(n, m);
if (ans1 < ans2)
{
cout << ans1 << '\n';
ll d = exgcd(m, n, y, s);
s = -s;
s *= (sum - ans1) / gcd(n, m);
cout << (s % m + m) % m << ' ' << 0 << '\n';
}
else
{
cout << ans2 << '\n';
ll d = exgcd(m, n, y, s);
s = -s;
s *= (sum + n * (n + 1) / 2 - ans2) / gcd(n, m);
cout << (s % m + m) % m << ' ' << 1 << '\n';
}
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
6 24 1 1 4 5 1 4
output:
1 18 1
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
7 29 1 9 1 9 8 1 0
output:
0 25 1
result:
ok ok
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3580kb
input:
1 1 0
output:
0 0 1
result:
wrong answer Integer parameter [name=d] equals to 1, violates the range [0, 0]