传送门
题意简述：求满足ax+by+c≤0ax+by+c\le0ax+by+c≤0的二元组(x,y)(x,y)(x,y)对数。
思路：
类欧几里得算法模板题。
把式子变化一下变成：求满足0≤y≤−ax+cb0\le y\le\frac{-ax+c}b0≤y≤b−ax+c的二元组(x,y)(x,y)(x,y)对数。
然后就变成求∑i=0⌊ca⌋⌊−ax+cb⌋+1\sum_{i=0}^{\left\lfloor\frac ca\right\rfloor}\left\lfloor\frac{-ax+c}b\right\rfloor+1∑i=0⌊ac⌋⌊b−ax+c⌋+1
直接上类欧几里得即可，注意处理负数的情况。
不会类欧几里得算法的点这里
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
ll a,b,c;
inline ll solve(ll a,ll b,ll c,ll n){
if(!n)return b/c;
if(n==1)return (a+b)/c+b/c;
if(c<0)return solve(-a,-b,-c,n);
if(a>=c||b>=c)return solve(a%c,b%c,c,n)+n*(n+1)/2*(a/c)+(n+1)*(b/c);
if(!a)return 0;
if(a<0||b<0)return solve(a%c+c,b%c+c,c,n)+n*(n+1)/2*(a/c-1)+(n+1)*(b/c-1);
ll m=(a*n+b)/c;
return n*m-solve(c,-b+c-1,a,m-1);
}
int main(){
cin>>a>>b>>c;
cout<<c/a+1+solve(-a,c,b,c/a);
return 0;
}