牛客练习赛113

xqy2003 / 2023-07-09 / 原文

题目链接

c

考虑到 $x$ 为 $1$ , 我们可以枚举 $y$ 减了多少次 , 那么根据同余方程 $ sum + i * y + j * x \equiv 0 \space (mod \ n)$ , 注意 $y$ 次数 ($i$)枚举范围就是 $[0 , n - 1]$ , 超过 $n$ ,根据乘法取模的性质 ,超过 $n$ 会取模回 $[0 , n - 1]$

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

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	int n,p,x,q,y;
	std::cin >> n >> p >> x >> q >> y;
	
	int s = 0;
	for(int i = 0 ; i < n ; ++i) {
		int x ; std::cin >> x;
		(s += x) %= n;
	}
	
	ll mn = 1E18;
	for(int i = 0 ; i < n ; ++i) {
		int j = ( n - ( (s - 1ll * i * y % n) % n + n ) % n ) % n;
		mn = std::min(mn , 1ll * i * q + 1ll * j * p);
	}
	
	std::cout << mn << '\n';
	
	return 0;
}

D

同理上一问的做法 , 我们去枚举 $y$ 的减的次数 $i$ , 但此时 $x$ 为任意数

$j * x \equiv -(sum + i * y) \ (mod \ n)$ , 令 $-(sum + i * y)$ 在 $mod \ n$ 意义下为 $b$
问题转换为 $j * x \equiv b \ (mod \ n)$ , 求 $j$ 的最小值

$① : 方法一$
考虑到 $j$ 的范围也是$[0 , n - 1]$ , 直接预处理出所有的 $ k*i \ (mod \ n)$的值对应最小值 $k$ 即可 , $O(1)$ 直接查询 $b$ 即可

$② : 方法二$
对于 $j * x \equiv b \ (mod \ n)$ 求 $j$ 的做法 , 在乘法逆元中就有提及 , $j * x \equiv b \ (mod \ n)$ 等价于 $j * x + t * n \equiv b \ (mod \ n)$ , 求 $(x , n , b)$ 的不定方程再把 $j$最小非负数求出来即可 ( 注意不关心 $t$ 是多少 , 并不会限制 $j$ , 直接取模求最小值即可 )

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

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	ll n,p,x,q,y;
	std::cin >> n >> p >> x >> q >> y;
	
	ll s = 0;
	for(ll i = 0 ; i < n ; ++i){
		ll w ; std::cin >> w;
		s += w , s %= n;
	}
	
	std::vector<ll> mp(n , n);
	for(ll j = 0 ; j < n ; ++j) {
		ll t = j * x % n;
		mp[t] = std::min(mp[t] , j);
	}
	
	ll mn = 1E18;
	for(ll i = 0 ; i < n ; ++i) {
		ll t = 	( (s - i * y) % n + n ) % n;
		t = (n - t) % n;
		if(mp[t] < n) {
			mn = std::min(mn , i * q + mp[t] * p);
		}
	}
	
	if(mn == 1E18)
		std::cout << -1 << '\n';
	else 
		std::cout << mn << '\n';
		
	return 0;
}

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

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	
	ll n,p,x,q,y;
	std::cin >> n >> p >> x >> q >> y;
	
	ll s = 0;
	for(ll i = 0 ; i < n ; ++i) {
		ll w ; std::cin >> w;
		( s += w ) %= n; 
	}
	
	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 = x1 , y2 = y1;
		x1 = y2;
		y1 = x2 - a / b * y2;
		return d;
		
	};
	
	ll mn = 1E18,a,b;
	ll d = exgcd(x , n , a , b);
	ll mod = n / d;
	
	for (ll j = 0 ; j < n ; ++j) {
		
		ll t =  ( (s - j * y) % n + n ) % n;
		t = (n - t) % n;
		
		ll _a = a;
		if(t % d != 0) continue;
		_a = _a * t / d;	
		_a =( _a % mod + mod ) % mod;
		mn = std::min(mn , j * q + _a * p); 
	
	}
	
	if(mn == 1E18)
		std::cout << -1 << '\n';
	else
		std::cout << mn << '\n';
		
	return 0;
}

想到了杭州站的 $A$ 和江西省赛 B