去年暑假打过一次,但是当时太菜,今天看到之前写过,好奇多少分,考后交了一发,发现自己是真的菜
然后,就算开了个坑吧,四道题。。。
\(exgcd\)板子
然后,\(exgcd\)咋用来着?
滚回去学数论基础了
#include <cstdio> using namespace std; #define int long long int min(int x, int y) { return x < y ? x : y; } int max(int x, int y){return x > y ? x : y;} int abs(int x) { return x < 0 ? -x : x; } void swap(int &x, int &y){x ^= y; y ^= x; x ^= y;} int exgcd(int a, int b, int &x, int &y){ if(b == 0){ x = 1; y = 0; return a; } int gcd = exgcd(b, a % b, y, x); y = y - a / b * x; return gcd; } signed main(){ int n, a, b; scanf("%lld%lld%lld", &n, &a, &b); int x, y; if(a > b)swap(a, b); int gcd = exgcd(a, b, x, y); b = b / gcd; a = a / gcd; x = (x % b + b) % b; int ans = 0; bool flag = 1; for (int i = 1; i <= n; ++i){ int now; scanf("%lld",&now); now = abs(now); if(now % gcd)flag = 0; if(flag){ now = now / gcd; int nx = (x * now % b + b) % b; int ny = (now - a * nx) / b; ans += min(abs(nx) + abs(ny), abs(nx - b) + abs(ny + a)); } } if(flag)printf("%lld\n", ans); else printf("-1\n"); return 0; }