QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#714531#5301. Modulo Ruins the LegendcbdsopaWA 3ms3936kbC++141.7kb2024-11-05 23:57:002024-11-05 23:57:00

Judging History

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

  • [2024-11-05 23:57:00]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3936kb
  • [2024-11-05 23:57:00]
  • 提交

answer

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define db double
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define sky fflush(stdout)
#define gc getchar
#define pc putchar
namespace IO{
	template<class T>
	inline void read(T &s){
		s = 0;char ch = gc();bool f = 0;
		while(ch < '0' || '9'<ch) {if(ch == '-') f = 1; ch = gc();}
		while('0'<=ch && ch<='9') {s = s * 10 + (ch ^ 48); ch = gc();}
		if(ch == '.'){
			T p = 0.1;ch = gc();
			while('0' <= ch && ch <= '9') {s = s + p * (ch ^ 48);p /= 10;ch = gc();}
		}
		s = f ? -s : s;
	}
	template<class T,class ...A>
	inline void read(T &s,A &...a){
		read(s); read(a...);
	}
	template<class T>
	inline void print(T x){
		if(x<0) {x = -x; pc('-');}
		static char st[40];
		static int top;
		top = 0;
		do{st[++top] = x - x / 10 * 10 + '0';} while(x /= 10);
		while(top) {pc(st[top--]);}
	}
	template<class T,class ...A>
	inline void print(T s,A ...a){
		print(s); print(a...);
	}
};
using IO::read;
using IO::print;
ll n, m;
ll exgcd(ll a, ll b, ll &x, ll &y){
	if(!b){
		x = 1; y = 0;
		return a;
	}
	ll d = exgcd(b, a % b, y, x);
	y -= (a / b) * x;
	return d;
}
int main(){
	//file(a);
	read(n, m);
	ll sum = 0;
	for(int i = 1; i <= n; ++i){
		ll x; read(x);
		sum += x;
	}
	ll s = 0, d = 0, k = 0, t = 0;
	ll g = exgcd(n, 1ll * n * (n + 1) / 2, s, d);
	ll g2 = exgcd(g, m, k, t);
	s *= k; d *= k;
	sum %= m;
	//g2 %= m;
	printf("%lld\n", sum % g2);
	ll t2 = sum / g2;
	int S = (m - (s * t2 % m + m) % m) % m;
	int D = (m - (d * t2 % m + m) % m) % m;
	printf("%d %d\n", S, D);
	return 0;
}
/*
sum + n * s + n * (n + 1) / 2 * d - m * t == r
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3824kb

input:

6 24
1 1 4 5 1 4

output:

1
15 19

result:

ok ok

Test #2:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

7 29
1 9 1 9 8 1 0

output:

0
0 0

result:

ok ok

Test #3:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

1 1
0

output:

0
0 0

result:

ok ok

Test #4:

score: 0
Accepted
time: 0ms
memory: 3936kb

input:

1 1000000000
963837005

output:

0
0 36162995

result:

ok ok

Test #5:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

2 1
0 0

output:

0
0 0

result:

ok ok

Test #6:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

2 1000000000
948507269 461613424

output:

0
410120693 589879307

result:

ok ok

Test #7:

score: 0
Accepted
time: 1ms
memory: 3796kb

input:

100000 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

0
0 0

result:

ok ok

Test #8:

score: 0
Accepted
time: 3ms
memory: 3836kb

input:

100000 1000000000
253614966 278270960 980235895 498158918 928430170 216003119 852570558 948400590 239257296 897053667 294741176 38297441 382677590 406314557 609468973 854148232 314532767 738191551 158215002 5865825 920471826 380037058 356271728 749175327 28319049 208101105 953758995 896570758 521930...

output:

46613
535950000 999989281

result:

ok ok

Test #9:

score: -100
Wrong Answer
time: 3ms
memory: 3748kb

input:

100000 998244353
561002596 498658036 721339539 63377827 532179242 934651519 234198881 490149304 2056307 499913682 427679408 694677560 516580968 300129454 816286800 688594301 183049581 456627420 495848352 273497462 953217060 796225499 207179832 728054671 409492082 25003432 810431468 206421553 5569626...

output:

0
331050504 839886562

result:

wrong answer Result not equal to solution.