题目链接:A
题意:
给定一个序列 \(a\),让序列加上一个等差序列,求出总和 %$ m$ 的最小值以及等差序列的 \(s\) 和公差 \(d\)。
思路:
定义 \(a\) 序列总和为sum。
则求解的答案为 \((sum+n∗s+n∗(n+1)2∗d)\) %m 的最小值。
根据裴蜀定理得到原式等于 \(sum+x∗gcd(n,n∗(n+1)/2) + y * m\)
再裴蜀,\(sum + k∗g + y * m\)。
求该值的最小,这个值大于 0,所以最小应该是等于 \(m\),得到 \(k=⌈sum−mg⌉\)。
AC代码:
// -----------------
#include <iostream>
#include <cstring>
#include <algorithm>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);
#define endl '\n'
#define rep(i,x,y) for(int i = (x); i <= (y); i ++)
#define dec(i,y,x) for(int i = (y); i >= (x); i --)
#define int long long
using namespace std;
const int N = 1e5 + 7;
int a[N];
int n,m;
int exgcd(int a, int b, int &x, int &y)
{
if (!b)
{
x = 1; y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
void solve()
{
cin >> n >> m;
int sum = 0;
rep(i,1,n) cin >> a[i],sum += a[i];
sum %= m;
int x,y,s,d;
int g = exgcd(exgcd(n, (n+1)*n/2, s, d), m, x, y); // 两次扩欧
int k = (m - sum + g - 1) / g; // 求 k
cout << k * g + sum - m << endl;
x = x * k % m; // 乘当前倍数则为 x 的实际值
s = s * x % m; // 再后推需乘当前系数更新实际值
d = d * x % m;
cout << (s + m) % m << " " << (d + m) % m << endl; // 保证答案非负
}
signed main()
{
IOS
int T = 1;
//cin >> T;
while(T --) { solve(); }
return 0;
}
标签:int,sum,exgcd,扩欧,2022ICPC,序列,裴蜀,define
From: https://www.cnblogs.com/liqs2526/p/17551219.html