洛谷题目页面传送门 & codeforces题目页面传送门
有(2)个等差数列(a:a_i=a_1i+b_1(iinmathbb n),b:b_i=a_2i+b_2(iinmathbb n))。给定(l,r),求有多少个整数(nin[l,r])满足(n)既在(a)内又在(b)内。
(a_1,a_2inleft(0,2times10^9right]capmathbb z,b_1,b_2,l,rinleft[-2times10^9,2times10^9right]capmathbb z,lleq r)。
设(n)在(a)中是第(xinmathbb n)项,在(b)中是第(yinmathbb 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'+kdelta x\y=y'+kdelta yend{cases}(kinmathbb z))。但对于(x,y)还有一个特殊的条件,就是(x,yinmathbb 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''+kdelta x\y=y''+kdelta yend{cases}(kin mathbb n))。将(x=x''+kdelta x)带入(a_1x+b_1in[l,r])得
[a_1(x''+kdelta x)+b_1in[l,r]]
即
[a_1x''+a_1kdelta x+b_1in[l,r]]
即
[a_1kdelta xin[l-a_1x''-b_1,r-a_1x''-b_1]]
即
[kinleft[dfrac{l-a_1x''-b_1}{a_1delta x},dfrac{r-a_1x''-b_1}{a_1delta x}right]]
又因为(kinmathbb n),所以
[kinleft[maxleft(0,leftlceildfrac{l-a_1x''-b_1}{a_1delta x}rightrceilright),leftlfloordfrac{r-a_1x''-b_1}{a_1delta x}rightrfloorright]]
然后算出(k_{min},k_{max}),(max(0,k_{max}-k_{min}+1))就是答案。
最后吐槽一下,c++中的/
号是向零取整,也就是(<0)时上取整、(geq0)时下取整,(k)的解集中如果直接用/
号算会wa,然后心态爆炸。所以必须要将被除数和除数统一取绝对值,然后利用(leftlfloordfrac abrightrfloor+leftlceildfrac {-a}brightrceil=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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/600361.html