JZOJ 50001「雅礼集训2019 Day10」T3 加农炮 （类欧几里得+Stern-Brocot树）
Posted On 2019年4月2日
样例
样例输入 1
|
1 2 3 4 |
3 3 5 1 3 5 14 3 5 8 |
样例输出 1
|
1 2 3 |
1 2 3 1 3 5 |
数据范围
对于所有数据：
Solution
在Stern-Brocot树上二分斜率用类欧判断即可
代码又长又丑
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 |
#include <cstdio> #include <iostream> using namespace std; #define int long long typedef long long ll; inline int read() { int f=1,k=0;char c=getchar(); while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } const int inf=1e9; int gcd(const int a,const int b){return !b?a:gcd(b,a%b);} int n,m,k,gtmp; ll f(const int a,const int b,const int c,const int n) { if (n<0)return 0; if (!c)return 0; if (a>=c||b>=c)return 1ll*a/c*n*(n+1)/2+1ll*b/c*(n+1)+f(a%c,b%c,c,n); int m=(n*a+b)/c; return 1ll*m*n-f(c,c-b-1,a,m-1); } inline int get(const int n,const int x,const int y) { return f(y,0,x,n); } int ansxl,ansyl,ansxr,ansyr,awx,awy,//awl, awr; void invdfs(int l1 , int l2 , int r1 , int r2) //l1/l2 , r1/r2 { int tmp,x=l1+r1,y=l2+r2; if (y<=m&&x<=n) gtmp=f(y,0,x,n),tmp=gtmp+n+1-(m*x/y<n?max(0ll,gtmp-get(m*x/y,x,y)-(n-m*x/y)*m):0); else return; if (k==tmp)return(void)(awx=x,awy=y); if (k>tmp) { int l=1,r=min(!l1?inf:(n-x)/l1,(m-y)/l2),mid; while (l<r) { mid=((l+r)>>1)+1; int L1=l1,L2=l2,R1=l1*mid+r1,R2=l2*mid+r2; int X=L1+R1,Y=L2+R2; int x=X,y=Y; if (y<=m&&x<=n) gtmp=f(y,0,x,n),tmp=gtmp+n+1-(m*x/y<n?max(0ll,gtmp-get(m*x/y,x,y)-(n-m*x/y)*m):0); else { r=mid-1; continue; } if (k>tmp)l=mid;else r=mid-1; } invdfs(l1 , l2 , l1*l+r1 , l2*l+r2); } else { int l=1,r=min((n-x)/r1,(m-y)/r2),mid; awr>tmp-k&&(awr=tmp-k,ansxr=x,ansyr=y); while (l<r) { mid=((l+r)>>1)+1; int L1=l1+r1*mid,L2=l2+r2*mid,R1=r1,R2=r2; int X=L1+R1,Y=L2+R2; int x=X,y=Y; if (y<=m&&x<=n) gtmp=f(y,0,x,n),tmp=gtmp+n+1-(m*x/y<n?max(0ll,gtmp-get(m*x/y,x,y)-(n-m*x/y)*m):0); else { r=mid-1;continue; } if (k<tmp)l=mid;else r=mid-1; }invdfs(l1+r1*l , l2+r2*l , r1 , r2); } } void dfs(int l1 , int l2 , int r1 , int r2) { int tmp,y=l1+r1,x=l2+r2; if (y<=m&&x<=n) gtmp=f(y,0,x,n),tmp=gtmp+n+1-(m*x/y<n?max(0ll,gtmp-get(m*x/y,x,y)-(n-m*x/y)*m):0); else { return; } if (k==tmp)return(void)(awx=x,awy=y); if (k<tmp) { awr>tmp-k&&(awr=tmp-k,ansxr=x,ansyr=y); int l=1,r=min(!l1?inf:(n-x)/l1,(m-y)/l2),mid; while (l<r) { mid=((l+r)>>1)+1; int L1=l1,L2=l2,R1=l1*mid+r1,R2=l2*mid+r2; int Y=L1+R1,X=L2+R2; if (Y<=m&&X<=n) gtmp=f(Y,0,X,n),tmp=gtmp+n+1-(m*X/Y<n?max(0ll,gtmp-get(m*X/Y,X,Y)-(n-m*X/Y)*m):0); else { r=mid-1; continue; } if (k<tmp)l=mid;else r=mid-1; } dfs(l1 , l2 , l1*l+r1 , l2*l+r2); } else { int l=1,r=min((n-x)/r1,(m-y)/r2),mid; while (l<r) { mid=((l+r)>>1)+1; int L1=l1+r1*mid,L2=l2+r2*mid,R1=r1,R2=r2; int Y=L1+R1,X=L2+R2; int x=X,y=Y; if (y<=m&&x<=n) gtmp=f(y,0,x,n),tmp=gtmp+n+1-(m*x/y<n?max(0ll,gtmp-get(m*x/y,x,y)-(n-m*x/y)*m):0); else { r=mid-1; continue; } if (k>tmp)l=mid;else r=mid-1; } dfs(l1+r1*l , l2+r2*l , r1 , r2); } } inline void work() { int gg,tmp; ansxr=ansyr=awx=awy=-1; awr=inf; n=read()-1,m=read()-1,k=read(); k++; if (k<=m+1)return(void)(printf("%lld %lld\n",1ll,k)); --k; if ((n+1)*(m+1)-n-1<k)return(void)(printf("%lld %lld\n",k+n+1-(n+1)*(m+1)+1,1ll)); swap(n,m); ++k; dfs(0,1,1,1); if (awx!=-1)return(void)(gg=min(n/awx,m/awy),printf("%lld %lld\n",(awy)*gg+1,(awx)*gg+1)); if (awr!=inf) { tmp=min((n)/(ansxr),(m)/(ansyr)); printf("%lld %lld\n",ansyr+(tmp-1-awr)*ansyr+1,ansxr+(tmp-1-awr)*ansxr+1); return; } ansxr=ansyr=awx=awy=-1; awr=inf; int x=1,y=1; gtmp=f(y,0,x,n),tmp=gtmp+n+1-(m*x/y<n?max(0ll,gtmp-get(m*x/y,x,y)-(n-m*x/y)*m):0); if (k<=tmp) awr>tmp-k&&(awr=tmp-k,ansxr=x,ansyr=y); invdfs(0,1,1,1); if (awx!=-1)return(void)(gg=min(n/awx,m/awy),printf("%lld %lld\n",(awy)*gg+1,(awx)*gg+1)); tmp=min((n)/(ansxr),(m)/(ansyr)); printf("%lld %lld\n",ansyr+(tmp-1-awr)*ansyr+1,ansxr+(tmp-1-awr)*ansxr+1); } signed main() { for (int T=read(),t=1;t<=T;t++)work(); } |
Subscribe
0 评论