题解

腾渊之星

2025-08-05 17:08:06

发布于：上海

22阅读

0回复

0点赞

数论题目难得没边

#include <iostream>
using namespace std;
typedef long long ll;
ll mxx = -1e18, mxy = -1e18;
ll mnx = 1e18, mny = 1e18;
ll cnt;
ll exgcd(ll a, ll b, ll &x, ll &y){
    if(b == 0){
        x = 1;
        y = 0;
        cnt++;
        mxx = max(mxx, x);
        mxy = max(mxy, y);
        return a;
    }
    ll x1, y1;
    ll g = exgcd(b, a%b, x1, y1);
    mxx = max(mxx, x);
    mxy = max(mxy, y);
    mnx = min(mnx, x1);
    mny = min(mny, y1);
    x = y1;
    y = x1 - a/b*y1;
    cnt++;
    return g;
}
ll ceil_div(ll p, ll q){
    if(p == 0) return 0;
    if(p > 0) return (p + q - 1) / q;
    else return p / q;
}
ll floor_div(ll p, ll q){
    if(p % q == 0) return p / q;
    if(p < 0) return p / q - 1;
    else return p / q;
}
void solve(){
    ll a, b, c;
    cin >> a >> b >> c;
    ll x0, y0;
    ll g = exgcd(a, b, x0, y0);
    if(c % g != 0) { // 无解
        cout << -1 << endl;
        return ;
    }
    ll x1 = x0 * c / g;
    ll y1 = y0 * c / g;
    ll dx = b / g;
    ll dy = a / g;
    ll t_l = ceil_div(1 - x1, dx);
    ll t_r = floor_div(y1 - 1, dy);
    if(t_l <= t_r){// 有正整数解
        ll cnt = t_r - t_l + 1;
        ll x_min = x1 + dx * t_l;
        ll x_max = x1 + dx * t_r;
        ll y_min = y1 - dy * t_r;
        ll y_max = y1 - dy * t_l;
        cout << cnt << " " << x_min << " " << y_min << " " << x_max << " " << y_max << endl;
    }
    else{// 无正整数解
        ll xmin = (x1 % dx + dx) % dx;
        if(xmin == 0) xmin = dx;
        ll ymin = (y1 % dy + dy) % dy;
        if(ymin == 0) ymin = dy;
        cout << xmin << " " << ymin << endl;
    }
}
int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 1

腾渊之星

有了新的思路

#include <iostream>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
ll gcd(ll a, ll b){
    if(b == 0) return a;
    else return gcd(b, a % b);
}
bool exgcd(ll a, ll b, ll &x, ll &y, ll d){
    if(b == 0){
        if(d % a == 0){
            x = d / a;
            y = 0;
            return true;
        }
        return false;
    }
    ll x1, y1;
    bool res = exgcd(b, a % b, x1, y1, d);
    if(!res) return false;
    x = y1;
    y = x1 - a / b * y1;
    return true;
}
void solve(){
    ll a, b, c;
    cin >> a >> b >> c;
    ll d = gcd(a, b);
    ll x, y;
    bool res = exgcd(a, b, x, y, c);
    if(!res){
        cout << "-1\n";
        return ;
    }
    ll dx = b / d;
    ll dy = a / d;
    ll k = x % dx <= 0 ? x / dx - 1 : x / dx;
    ll xmin = x - k * dx;
    ll ymax = y + k * dy;
    k = y % dy <= 0 ? y / dy - 1 : y / dy;
    ll xmax = x + k * dx;
    ll ymin = y - k * dy;
    if(xmax <= 0 || ymax <= 0){
        // ll cnt = (xmax - xmin) / dx + 1;
        // cout << cnt << " " << xmin << " " << ymin << " " << xmax << " " << ymax << "\n";
        cout << xmin << " " << ymin << "\n";
        return ;
    }
    ll cnt = (xmax - xmin) / dx + 1;
    cout << cnt << " " << xmin << " " << ymin << " " << xmax << " " << ymax << "\n";
}
int main(){
    int t;
    cin >>t;
    while(t--) solve();
    return 0;
}
// gcd(a, b) = ax + by
// = gcd(b, a % b) = bx1 + (a - a / b * b)y1
// = ay1 + b(x1 - a / b * y1)

2025-08-10 来自上海