权限题。

题意：

给定a,b,c,求满足方程 Ax+By<=C 的非负整数解

A,B<=109,C<=min(A,B)∗109

Solution:

类欧几里得算法模板题

没学过的点击这里

变形一下这个式子：

y<=C−AxB

但是这个式子如果直接套用类欧几里得是包含负数的，我们需要想办法帮他变变形：考虑这个式子的几何意义：线段 y=C−AxB 和x轴，y轴所围成的图形中的整点的个数，我们再考虑类欧几里得的几何意义：一条倾斜直线与x=0和x=n两条铅垂线组成的直角梯形内整点数量，因此我们想办法变a为正，调整截距使得新直线在x轴上的切点>-1且<0（避免多算），因为我们最终要求的是整点数，所以说我们需要使我们最后求得的新直线与x轴的交点x1距最近的整点的距离等于原直线的交点x2距最近的整点的距离，这就要求 x1+x2∈z ,设新直线的斜率为d,那么 c−da=z ,即 c−d=az ,我们还要保证d尽量小，所以 d=c%a ,有了这些就可以直接套公式搞了

代码：

#include<cstdio>
#include<iostream>
using namespace std;
long long a,b,c;
long long f(long long a,long long b,long long c,long long n)
{
    if (!c) return 0;
    if (a<c&&b<c)
    {
        return ((a*n+b)/c)*n-f(c,c-b-1,a,(a*n+b)/c-1);
    }
    else return (a/c)*n*(n+1)/2+(b/c)*(n+1)+f(a%c,b%c,c,n);
}
int main()
{
    scanf("%lld%lld%lld",&a,&b,&c);
    printf("%lld",f(a,c%a,b,c/a)+c/a+1);
}