A. Modulo Ruins the Legend 2022 ICPC-杭州

本文主要是介绍A. Modulo Ruins the Legend 2022 ICPC-杭州，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：

（1）题目抽象为求（ns+n*(n+1)/2*d + sum)%m的最小值

（2)由裴属定理，ns+n*(n+1)/2*d = k1*g1(n,n*(n+1)/2);

 (3)所以为求（k1g1 + sum)%m = ans的最小值；

（4）即k1g1 +k2m = ans - sum;

（5）又k1g1 + k2m = k3g2(g1,m);

(6)即求k3g2 + sum = ans,中ans最小值，即sum%g2的最小值，直接取正模即可，这样我们就拿到了ans，再由拓展欧几里得求出k1，再拓展一次求出s,d即可，这时候值可能为负，由于全局对m取模，所以对s,d取正模即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>using namespace std;typedef long long LL;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;
}LL gcd(LL a,LL b)
{return b? gcd(b,a%b) : a;
}
LL MOD(LL a,LL b)
{return (a%b + b)%b;
}int main()
{LL n, m;cin >> n >> m;LL sum = 0;for (int i = 0; i < n; i++){LL x;cin >> x;sum += x;}LL ans,k1,k2,S,D;LL g1 = gcd(n,n*(n + 1)/2);LL g2 = gcd(g1,m);ans = MOD(sum,g2);g2 = exgcd(g1,m,k1,k2);k1 *= ( (ans - sum)/g2 ) % m;k1 %= m;g1 = exgcd(n,n*(n + 1)/2,S,D);S*= k1,D*= k1;S = MOD(S,m),D = MOD(D,m);cout << ans << endl;cout << S <<" "<<D;return 0;
}

这篇关于A. Modulo Ruins the Legend 2022 ICPC-杭州的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---