第一次AK

ax + by = n + 1
求所有满足上式的x, y 0 < x, y < n

题目描述

教练从左向右发苹果，每a个队员获得一个苹果（a号是第一个得到苹果的），从右往左发香蕉，每b个队员获得一个香蕉，（n-b+1)号是第一个得到香蕉的）。

问题：教练想要知道有多少队员既获得了苹果又获得了香蕉。

• 设编号为x的满足题意， 因此有x % a = 0, 倒过来的编号就是（n - x + 1）, (n - x + 1) % b = 0
• 因此设x = ka, n - x + 1 = tb, 结合两式得出， ka + tb = n + 1 很明显就是一个线性方程组
• k > 0, t > 0

#include <iostream>

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 g = exgcd(b, a % b, x, y);
    LL temp = x;
    x = y;
    y = temp - a / b * y;
    return g;
}

int main()
{
    LL n, a, b;
    cin >> n >> a >> b;
    LL x, y;
    LL d = exgcd(a, b, x, y);
    n ++;
    if(n % d)puts("0");
    else
    {
        LL px = b / d; //求出x的周期
        LL py = a / d; // 求出y的周期
        x = (n / d * x % px + px) % px;//求出最小的非负整数x
        y = (n / d * y % py + py) % py;//求出最小非负整数y
        if(!x)x = px;//如果x为0的话 增加一个周期
        if(x * a >= n || y * b >= n)puts("0");//如果x*a >= n 的话 y 一定小于等于0不满足，同理y * b
        else
        {
            LL k = n - a * x; // 求出b * y
            LL y = k / b; // 求出满足x最小正整数的情况下的y
            LL k1 = k / px; // 求出在不超过n的情况下还有多少x的周期满足
            if(k % px == 0)k1 --;//如果刚好==n的话必须剪掉一次
            LL k2 = y / py; // 同理看不超过n的情况下多少y的周期满足
            if(y % py == 0)k2 --; // 同理刚好为n的情况下剪掉一次
            cout << min(k1, k2) + 1 << endl;//取一个最小值，+1是因为进入else的情况就已经满足一个
        }

    }
    return 0;
}

更加简洁的版本

#include <iostream>
#include <cstring>

#define int long long
using namespace std;
typedef long long LL;

int exgcd(int a, int b, int &x, int &y)
{
    if(!b)
    {
        x = 1;
        y = 0;
        return a;
    }
    int g = exgcd(b, a % b, x, y);
    int temp = x;
    x = y;
    y = temp - a / b * y;
    return g;
}

signed main()
{
    int n, a, b;
    cin >> n >> a >> b;
    n ++;
    int res = 0, x, y;
    int d = exgcd(a, b, x, y);
    if(n % d)puts("0"); // 不存在就只有0
    else
    {
        x *= n / d;
        y *= n / d;
        int modx = b / d, mody = a / d;
        x = (x % modx + modx) % modx;
        if(!x) x += modx;
        y = (n - x * a) / b;
        if(y <= 0)puts("0");//最小的k值对应的t值小于等于0不满足
        else
        {
            int t = (y % mody != 0);// 如果ymod 周期不能整除就要上取整
            cout << y / mody + t<< endl;
        }
    }
    return 0;
}