QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#623849#5301. Modulo Ruins the Legend2317663977WA 0ms3660kbC++231.2kb2024-10-09 14:12:122024-10-09 14:12:12

Judging History

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

  • [2024-10-09 14:12:12]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3660kb
  • [2024-10-09 14:12:12]
  • 提交

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]