CodeForces 710D Two Arithmetic Progressions
2020-03-06 16:01:18来源:博客园 阅读 ()
CodeForces 710D Two Arithmetic Progressions
Exgcd,C++中/号的feature处理洛谷题目页面传送门 & CodeForces题目页面传送门
有\(2\)个等差数列\(A:A_i=a_1i+b_1(i\in\mathbb N),B:B_i=a_2i+b_2(i\in\mathbb N)\)。给定\(l,r\),求有多少个整数\(n\in[l,r]\)满足\(n\)既在\(A\)内又在\(B\)内。
\(a_1,a_2\in\left(0,2\times10^9\right]\cap\mathbb Z,b_1,b_2,l,r\in\left[-2\times10^9,2\times10^9\right]\cap\mathbb Z,l\leq r\)。
设\(n\)在\(A\)中是第\(x\in\mathbb N\)项,在\(B\)中是第\(y\in\mathbb N\)项,则可以列出不定方程
\[a_1x+b_1=a_2y+b_2\]
转化成标准形式,得
\[a_1x-a_2y=b_2-b_1\]
这个显然可以用Exgcd先确定无解并输出\(0\)走人,或确定有解并得到一组特解\(\begin{cases}x=x'\\y=y'\end{cases}\)。令\(\Delta x=\dfrac{a_2}{\gcd(a_1,a_2)},\Delta y=\dfrac{a_1}{\gcd(a_1,a_2)}\),则通解是\(\begin{cases}x=x'+k\Delta x\\y=y'+k\Delta y\end{cases}(k\in\mathbb Z)\)。但对于\(x,y\)还有一个特殊的条件,就是\(x,y\in\mathbb N\)。不难发现\(x,y\)同增同减,不妨找到使得\(x,y\)都最小的一组解\(\begin{cases}x=x''\\y=y''\end{cases}\)。\(x,y\)都最小,当且仅当\(x-\Delta x<0\)或\(y-\Delta y<0\),于是分别令\(x''=x'\bmod \Delta x,y''=y'\bmod \Delta y\),每次带入原方程解出另一个变量看是否\(\geq0\),必有一次合法。
现在知道了\(x'',y''\),通解就变成了\(\begin{cases}x=x''+k\Delta x\\y=y''+k\Delta y\end{cases}(k\in \mathbb N)\)。将\(x=x''+k\Delta x\)带入\(a_1x+b_1\in[l,r]\)得
\[a_1(x''+k\Delta x)+b_1\in[l,r]\]
即
\[a_1x''+a_1k\Delta x+b_1\in[l,r]\]
即
\[a_1k\Delta x\in[l-a_1x''-b_1,r-a_1x''-b_1]\]
即
\[k\in\left[\dfrac{l-a_1x''-b_1}{a_1\Delta x},\dfrac{r-a_1x''-b_1}{a_1\Delta x}\right]\]
又因为\(k\in\mathbb N\),所以
\[k\in\left[\max\left(0,\left\lceil\dfrac{l-a_1x''-b_1}{a_1\Delta x}\right\rceil\right),\left\lfloor\dfrac{r-a_1x''-b_1}{a_1\Delta x}\right\rfloor\right]\]
然后算出\(k_{\min},k_{\max}\),\(\max(0,k_{\max}-k_{\min}+1)\)就是答案。
最后吐槽一下,C++中的/
号是向零取整,也就是\(<0\)时上取整、\(\geq0\)时下取整,\(k\)的解集中如果直接用/
号算会WA,然后心态爆炸。所以必须要将被除数和除数统一取绝对值,然后利用\(\left\lfloor\dfrac ab\right\rfloor+\left\lceil\dfrac {-a}b\right\rceil=0\)这个原理计算,最后该取相反数取相反数:
int div_floor(int x,int y){return (x<0)^(y<0)?-(abs(x)+abs(y)-1)/abs(y):x/y;}
int div_ceil(int x,int y){return (x<0)^(y<0)?-abs(x)/abs(y):(x+y-1)/y;}
下面贴AC代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
int div_floor(int x,int y){return (x<0)^(y<0)?-(abs(x)+abs(y)-1)/abs(y):x/y;}//下取整
int div_ceil(int x,int y){return (x<0)^(y<0)?-abs(x)/abs(y):(x+y-1)/y;}//上取整
int exgcd(int a,int b,int &x,int &y){//Exgcd
if(!b)return x=1,y=0,a;
int d=exgcd(b,a%b,y,x);
return y-=a/b*x,d;
}
int a1,a2,b1,b2,l,r;//题目给的参数
signed main(){
cin>>a1>>b1>>a2>>b2>>l>>r;
int x,y,gcd=exgcd(a1,-a2,x,y);
if((b2-b1)%gcd)return puts("0"),0;//无解
x*=(b2-b1)/gcd;y*=(b2-b1)/gcd;//找到特解
int dx=abs(a2/gcd),dy=abs(a1/gcd);
((x%=dx)+=dx)%=dx;y=(a1*x-(b2-b1))/a2;
if(y<0)((y%=dy)+=dy)%=dy,x=(a2*y+(b2-b1))/a1;//找到使x,y都最小的解
int l0=max(0ll,div_ceil(l-a1*x-b1,a1*dx)),r0=div_floor(r-a1*x-b1,a1*dx);//k[min],k[max]
cout<<max(0ll,r0-l0+1);//答案
return 0;
}
原文链接:https://www.cnblogs.com/ycx-akioi/p/CodeForces-710D.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- CodeForces 1326E - Bombs 2020-03-25
- CodeForces 1320D - Reachable Strings 2020-03-20
- CodeForces 1324 - Codeforces Round #627 (Div. 3) 2020-03-13
- CodeForces 1313D Happy New Year 2020-03-04
- CodeForces 1313E Concatenation with intersection 2020-03-02
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash