题意

求满足如下不等式的非负整数 \(x,y\) 的对数

\[ax+by\leq c
\]

Sol

a,b,c 都是非负的,那么先随便变个形:

\[y\leq\frac{c-ax}{b}
\]

显然答案就是:

\[\sum_{x=0}^{\lfloor\frac{c}{a} \rfloor}\bigg(\lfloor \frac{c-ax}{b}\rfloor+1\bigg)
\]

类欧板子题了，但是这个斜率居然是一个负数，不能直接套用以前的做法。

一开始想着先把这条直线往 \(x\) 轴对称然后向上平移，但是这样太麻烦了。

令 \(n=\lfloor \frac{c}{a}\rfloor\) ，直接把直线沿着 \(n/2\) 对称就好了，这样在下方的点不受影响，左上方的点也被对应到了右上方，并且整点依然是整点。

code：

#include<bits/stdc++.h>

using namespace std;

template<class T>inline void init(T&x){

	x=0;char ch=getchar();bool t=0;

	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;

	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);

	if(t) x=-x;return;

}typedef long long ll;

ll a,b,c;

inline ll gcd(ll a,ll b){return b? gcd(b,a%b):a;}

inline ll likegcd(ll n,ll a,ll b,ll c){

	if(!n) return b/c;if(!a) return b/c*(n+1);

	ll d=abs(gcd(gcd(a,b),c));

	if(d>1) a/=d,b/=d,c/=d;

	if(a>=c||b>=c) return b/c*(n+1)+a/c*(n+1)*n/2+likegcd(n,a%c,b%c,c);

	ll m=(a*n+b)/c;

	return n*m-likegcd(m-1,c,c-b-1,a);

}

int main()

{

	init(a),init(b),init(c);

	ll n=c/a;ll ans=n+1+likegcd(n,a,c-a*n,b);

	cout<<ans<<endl;

	return 0;

}

巴特西

【LuoguP5171】Earthquake

题意

Sol

最新文章

热门文章