这是我的独家解法，快去关注这个人！

场上秒完看一眼题解区发现没有大佬和我一个解法，遂一发题解。

思路

首先第一步和题解区大佬一样，把解的个数变成这个式子：

$$\sum_{x=0}^{\lfloor \frac{c}{a} \rfloor}\lfloor \frac{c-ax}{b} \rfloor +1$$

一眼类欧。

然后题解区的大佬们就开始加 $x$，但是作为蒟蒻的我是永远想不到的（我还是太菜了），于是我用了一个新奇的方法。

由于类欧的几个参数是不能有负数的，所以现在要做的是将 $x$ 的系数 $-a$ 转正。

令 $v= \lfloor \frac{c}{a} \rfloor$。

由 $x,y \in \mathbb N$ 得 $c-ax \ge 0$，即 $x \in [0,v]$。

因为本题求的是非负整数解的个数，所以 $x$ 的取值与解无关。

所以我们再令 $x'=v-x$，同样的 $x' \in [0,v]$，于是 我们就可以把解的个数变成这样：

$$\sum_{x'=0}^{\lfloor \frac{c}{a} \rfloor} \lfloor \frac{c-a(v-x')}{b} \rfloor+1$$

将 $1$ 代入式子中，整理得：

$$\sum_{x'=0}^{\lfloor \frac{c}{a} \rfloor} \lfloor \frac{ax'+c+b-av}{b} \rfloor$$

剩下就是裸类欧了，套板子即可。

警示后人：本题不需要取模（我当成类欧基本操作取模卡了十分钟）。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ac (a/c)
#define bc (b/c)
#define gs(n) n*(n+1)/2
int f(int a,int b,int c,int n)
{
	if(a==0)return bc*(n+1);
	if(n==0)return bc;
	if(a>=c||b>=c)
	{
		int sum=f(a%c,b%c,c,n);
		sum=(sum+gs(n)*ac+(n+1)*bc);
		return sum;
	}
	int m=(a*n+b)/c;
	int sum=f(c,c-b-1,a,m-1);
	return (n*m-sum);
}
signed main()
{
	int a,b,c;cin>>a>>b>>c;
	int v=c/a;
	int res=f(a,c+b-a*v,b,v);
	cout<<res;
	return 0;
}

前置知识

【提高数学】类欧几里得算法的盛宴

题意简述

给定 $a,b,c$，求 $ax+by \le c$ 非负整数解的个数，我们可以转换：

$$ax+by \le c\ \to\ by\le c-ax$$ $$by\le c-ax\ \to\ y\le\left\lfloor{\dfrac{c-ax}{b}}\right\rfloor$$

对于 $y$，合法的 $x$ 的个数是 $\left\lfloor{\dfrac{c-ax}{b}}\right\rfloor+1$，之所以要 $+1$ 是因为符号是 $\le$。

令 $y=0$，此时存在 $ax\le c$，即 $x\le\left\lfloor\dfrac{c}{a}\right\rfloor$，那么我们需要枚举的 $x$ 范围是 $0\sim\left\lfloor\dfrac{c}{a}\right\rfloor$。

进一步将要求的量表述出来，即在每一个 $x$ 的情况下，计算存在多少个合法解，即：

$$\sum\limits_{x=0}^{\left\lfloor\frac{c}{a}\right\rfloor}\left\lfloor{\dfrac{c-ax}{b}}\right\rfloor+1$$

诶，长得，是不是有点像类欧？然而你也不能直接把 $-b$ 代入计算，那么我们转换，用类似于 JZP 题解的方式，在分子加入 $bx$，在外部减去 $\left\lfloor{\dfrac{bx}{b}}\right\rfloor$，即 $x$，式子就变成：

$$\sum\limits_{x=0}^{\left\lfloor\frac{c}{a}\right\rfloor}\left\lfloor{\dfrac{(b-a)x+c}{b}}\right\rfloor-x+1$$

为了能用类欧，我们需要让 $b-a>0$，那么就在 $b<a$ 时使用 $\text{swap}(a,b)$，这样就处理完毕。对于式子的第一部分：

$$\sum\limits_{x=0}^{\left\lfloor\frac{c}{a}\right\rfloor}\left\lfloor{\dfrac{(b-a)x+c}{b}}\right\rfloor$$

已经可以用 $\text{Akin\ Euclidean}(b-a,c,b,\frac{a}{c})$ 来解决了。

但我们发现这个 $x$ 不好处理，于是我们单独拿出来：

$$\sum\limits_{x=0}^{\left\lfloor\frac{c}{a}\right\rfloor}-x+1$$

用基本的等差数列来求和得到：

$$\dfrac{\left(0+\left\lfloor\frac{c}{a}\right\rfloor\right)\times\left(\left\lfloor\frac{c}{a}\right\rfloor+1\right)}{2}+\left\lfloor\frac{c}{a}\right\rfloor$$

其中，大概是这样：

• $0$ 是首项

• $\left\lfloor\frac{c}{a}\right\rfloor$ 是末项

• 项数是 $\left\lfloor\frac{c}{a}\right\rfloor+1$

• 在这个式子后的那个 $\left\lfloor\frac{c}{a}\right\rfloor$ 是 $1$ 对整个求和式子的贡献

那么我们直接套到原式当中就是：

$$\left(\sum\limits_{x=0}^{\left\lfloor\frac{c}{a}\right\rfloor}\left\lfloor{\dfrac{(b-a)x+c}{b}}\right\rfloor\right)+\dfrac{\left\lfloor\frac{c}{a}\right\rfloor\left(\left\lfloor\frac{c}{a}\right\rfloor+1\right)}{2}+\left\lfloor\frac{c}{a}\right\rfloor$$

那么推导结束。

代码实现

如下，其中的 $f$ 函数就是类欧几里得函数。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a,b,c,s;
int f(int a,int b,int c,int n){
    if(a==0)return((b/c)*(n+1));
    if(a>=c||b>=c)return f(a%c,b%c,c,n)+(a/c)*n*(n+1)/2+(b/c)*(n+1);
    int m=(a*n+b)/c;
    return n*m-f(c,c-b-1,a,m-1);
}signed main() {
	cin>>a>>b>>c;if(b<a)swap(b,a);
	cout<<f(b-a,c,b,c/a)-(c/a)*(c/a+1)/2+(c/a)+1<<endl;
	return 0;
}