[atAGC045F]Division into Multiples

令$d=\gcd(a,b)$，可以发现$c|(ax+by)$等价于$lcm(c,d)|(ax+by)$，因此不妨令$c'=lcm(c,d)$，然后将$a$、$b$和$c$同时除以$d$

接下来设$(a,c)=d_{1}$，根据整除的传递性有$d_{1}|(ax+by)$，由于$d_{1}|ax$，可得$d_{1}|by$，又因为$(b,d_{1})=1$，所以$d_{1}|y$

因此，可以令$y'=\lfloor\frac{y}{d}\rfloor$，然后再将$a$和$c$同除以$d_{1}$，$b$和$c$类似，最后可以令$a$、$b$和$c$两两互素

令$D\equiv \frac{a}{b}(mod\ c)$（由于$(b,c)=1$因此存在），对于$ax+by\equiv 0(mod\ c)$，可得$y\equiv -xD(mod\ c)$，取其中最小非负整数解为$Y_{x}$（特别的，当$x=0$时取$Y_{x}=c$）

$x$的范围为$[0,c]$，同时对于$x_{1}<x_{2}$，若$Y_{x_{1}}\le Y_{x_{2}}$则后者没有意义，可以通过维护一个栈，从小到大枚举$x$，若栈顶小于$Y_{x}$则将$Y_{x}$加入栈中

构造：对于一个二维平面，有一个点$(x',y')$（初始为$(0,0)$），每一次令$x'$和$y'$分别加1，然后若$x'>c$则$x'$减去$c$，若$y'\ge D$（注意等号不同）则$y'$减去$D$

当$y'=0$时，其实就对应于$x=\frac{times}{D}$和$Y_{x}=c-x'$（其中$times$为加1的次数），前者依次遍历所有$x$，因此即若$c-x'$小于栈顶时就将$c-x'$压入栈中

但此时这样的复杂度反而退化为$o(cD)$，因此考虑递归缩小$c$和$D$的范围

注意到这样两个性质：

1.当我们位于$(x',y')$，若$x'>0$且$y'+c<D$，则$c$步后必然移动到$(x',y'+c)$，由此可以令$D$不断减去$c$直至$D\le c$

注意两个细节：1.当$x'=0$，$c$步后会移动到$(c,y'+D)$；2.当$c=D$时不能减，原因同上

2.当我们位于$(x',y')$，若$x'+D\le c$且$c-(x'+D-y')$不小于栈顶则$D$步后会移动到$(x'+D,y')$，因此考虑令$t=\lfloor\frac{c}{D}\rfloor$，当$c-tD$加入栈后，可以看作$c'=c-tD$的子问题

简单模拟前面几步，不难发现一开始栈中会插入$c,c-D,...,c-tD$，因此先将这个插入后即可缩小$c$

（这里的栈其实是有重复元素的，这次的$c-tD$和下一次的$c'$是相同的，暂时看作两个不同的数）

这就是一个欧几里得的过程，因此复杂度为$o(\log_{2}c)$，且栈中至多有$o(\log_{2}c)$个等差序列（由于复杂度限制，这个栈需要通过若干个等差数列来描述）

（另外这样的过程并不容易维护$times$，但可以通过$Y_{x}$来找到最小的$x$，即$x\equiv -\frac{Y_{x}}{D}(mod\ c)$）

有两个结论：1.对于一个等差数列，由$Y_{x}$所构造出来的$x$也是等差数列；2.$x$和$Y_{x}$的等差数列公差严格单调递增（注意$Y_{x}$为负数）

由这些结论，当我们必然存在一组最优解使得取得所有组都在同一个等差数列中

反证法，假设取了第$i$个等差数列中第$i'$项和第$j$个等差数列中第$j'$项的组合（其中$i<j$），由于$i$的末尾=$i+1$的开头（$j$的开头=$j-1$的末尾），强制$i'$（$j'$）不能为等差数列中最后一项（第一项）

此时，不妨令$i'$取该等差数列的后一项，$j'$取该等差数列中前一项，分别对$x$和$y$分析：记$i$和$j$两个等差数列中$x$的公差分别为$d_{i}$和$d_{j}$，相比较而言$\Delta x=d_{i}-d_{j}<0$，因此更优（$y$同理）

对于一个等差数列中，可以二分枚举答案，先取等差数列中第一个，之后调整一定是$x+=d_{x}$且$y-=d_{y}$（这里的$x$和$y$只所需的数量，不是限制），最多调整$ans\cdot (len-1)$（$len$为等差数列长度），简单判定即可

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define ll long long

 4 int t,a,x,b,y,c,d,s,D,inv_D,ans;

 5 int gcd(int x,int y){

 6     if (!y)return x;

 7     return gcd(y,x%y);

 8 }

 9 int exgcd(int a,int b,int &x,int &y){

10     if (!b){

11         x=1;

12         y=0;

13         return a;

14     }

15     int d=exgcd(b,a%b,y,x);

16     y-=(a/b)*x;

17     return d;

18 }

19 int inv(int k,int p){

20     int x,y;

21     exgcd(k,p,x,y);

22     return (x%p+p)%p;

23 }

24 ll div1(ll x,int y){

25     //t*y>=x

26     if (x<=0)return 0;

27     return (x+y-1)/y;

28 }

29 ll div2(ll x,int y){

30     if (x<0)return -1;

31     return x/y;

32 }

33 int query(int ay,int dy,int cnt){

34     int ax=c-1LL*ay*inv_D%c;

35     if (ay)ax%=c;

36     int dx=1LL*dy*inv_D%c;

37     int l=0,r=x+y;

38     while (l<r){

39         int mid=(l+r+1>>1);

40         //存在t使得ax*mid+t*dx<=x,ay*mid-t*dy<=y,0<=t<=cnt*mid

41         if (div1(1LL*ay*mid-y,dy)<=min(div2(x-1LL*ax*mid,dx),1LL*cnt*mid))l=mid;

42         else r=mid-1;

43     }

44     return l;

45 }

46 int main(){

47     scanf("%d",&t);

48     while (t--){

49         scanf("%d%d%d%d%d",&a,&x,&b,&y,&c);

50         d=gcd(a,b);

51         c/=gcd(c,d),a/=d,b/=d;

52         d=gcd(a,c);

53         y/=d,a/=d,c/=d;

54         d=gcd(b,c);

55         x/=d,b/=d,c/=d;

56         if (c==1){

57             printf("%d\n",x+y);

58             continue;

59         }

60         D=1LL*a*inv(b,c)%c;

61         inv_D=inv(D,c);

62         int cc=c,dd=D;

63         ans=0;

64         while (cc){

65             if (cc<dd)dd=(dd-1)%cc+1;

66             else{

67                 int t=cc/dd;

68                 ans=max(ans,query(cc,dd,t));

69                 cc-=t*dd;

70             }

71         }

72         printf("%d\n",ans);

73     }

74 }

巴特西

[atAGC045F]Division into Multiples

最新文章

热门文章