2022 ICPC 杭州站

xqy2003 / 2023-07-09 / 原文

题目链接

A

问题等价于求 \(ans = (\sum_{i = 1}^{n}a_{i} + n * s + \frac{n(n+1)}{2}* d ) \ \% \ m\) 的最小值
记 \(\sum_{i = 1}^{n}a_{i} \% \ m\) 为 \(sum\) , \(n * s + \frac{n(n+1)}{2}* d = c * g1\) , 其中\(g1 = gcd(n , \frac{n(n+1)}{2})\)

问题转换化为 \((sum + c * g1) \ \% \ m\) 的最小值 , 此时等价于 \((sum + c * g1 + t * m) \ \% \ m\)
令 \(c * g1 + t * m = q * g2\) , 其中 \(g2 = gcd(g1 , m)\) , 式子转换为 \((sum + q * g2) \ \% \ m\)的最小值 , 此时由于 \(g2 \ | \ m\) , 余数循环节的大小就是 \(\frac{m}{g2}\) , 当 \(q = \lceil \frac{m - sum}{g2} \rceil\)时 , 有整体式子在取模意义下的最小值

#include <bits/stdc++.h>
using ll = long long;

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	ll n,m;
	std::cin >> n >> m;
	
	ll sum = 0;
	for(int i = 0 ; i < n ; ++i) {
		ll x ; std::cin >> x;
		( sum += x ) %= m; 
	}
	
	std::function<ll(ll,ll,ll&,ll&)> exgcd = [&](ll a,ll b,ll &x1,ll &y1) {
		if(!b) {
			x1 = 1 , y1 = 0;
			return a;
		}
		
		ll d = exgcd(b , a % b , x1 , y1);
		ll x2,y2;
		x2 = x1 , y2 = y1;
		x1 = y2;
		y1 = x2 - a / b * y2;
		return d;
	};
	
	
	ll x_s,x_d;
	ll g1 = exgcd(n , (n + 1) * n / 2 , x_s , x_d);
	
	ll x_g1,y_m;
	ll g2 = exgcd(g1 , m , x_g1 , y_m);
	
	ll q = (m - sum + g2 - 1) / g2;
	
	ll ans = (sum + q * g2 % m) % m;
	ll s = q * x_g1 % m * x_s % m , d = q * x_g1 % m * x_d % m;
	
	s = ( (s % m) + m ) % m , d = ( (d % m) + m ) % m;
	
	std::cout << ans << '\n';
	std::cout << s << ' ' << d << '\n';
	
	return 0;
}