类欧几里得算法|[类欧几里得算法数论] BZOJ 2987 Earthquake 类欧几里得算法|数论

第一道类欧题其实是裸题啦
手推

文章图片

#include #include #include using namespace std; typedef long long ll; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; } return *p1++; }inline void read(ll &x) { char c=nc(),b=1; for (; !(c>='0' && c<='9'); c=nc()) if (c=='-') b=-1; for (x=0; c>='0' && c<='9'; x=x*10+c-'0',c=nc()); x*=b; }inline ll Solve(ll n,ll a,ll c,ll b){ if (!a) return (c/b)*n; if (c<0){ ll t=(-c+b-1)/b; return Solve(n,a,c+t*b,b)-t*n; } if (b<=c) return Solve(n,a,c%b,b)+n*(c/b); if (a>=b) return n*(n+1)/2*(a/b)+Solve(n,a%b,c,b); ll kmax=(c+a*n)/b; ll ret=(n+1)*kmax; ret-=Solve(kmax,b,a-1-c,a); return ret; }ll ans; int main() { ll a,b,c; freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(a); read(b); read(c); ans=(c/b)+(c/a)+1+Solve(c/a,a,c%a-a,b); printf("%lld\n",ans); return 0; }

【类欧几里得算法|[类欧几里得算法数论] BZOJ 2987 Earthquake】