bzoj5027 数学题

bzoj5027 数学题

​​ Description 给出a,b,c,x1,x2,y1,y2，求满足ax+by+c=0，且x∈[x1,x2],y∈[y1,y2]的整数解有多少对？ Input 第一行包含7个整数，a,b,c,x1,x2,y1,y2，整数间用空格隔开。 a,b,c,x1,x2,y1,y2的绝对值不超过10^8。 Output 输出整数解有多少对？ Sample Input 1 1 -3 0 4 0 4 Sample Output 4 题解待填坑吧先.. 看到方程 一元二次方程是不是可以想到之前Noip2012有一道同余方程的题运用扩展欧几里得可以解一元二次方程 还可以求逆元 扩展欧几里得可以求ax+by=gcd(a,b)的一组解 那么我们可以把ax+by+c=0;同除gcd(a,b) 然后再算x,y就可以了 如果c不能整除gcd(a,b)说明 原方程并没有整数解 不妨我们把两边÷gcd(a,b)*c就能得到ax+by+c=0这个不定方程的一组整数解 有了一组整数解我们就可以o1算出在x1~x2 y1~y2范围内的整数解个数了 设一组整数解分别为x0,y0 那么其他整数解a(x0+kdx)+b(y0+kdy)+c=0; 可知akdx+bkdy=0; a*dx=b*dy那么我们想得到dx的最小整数就是当a*dx&b*dy都是他们的lcm时即可 所以dx=lcm(a,b)/a=b/gcd(a,b) dy同理 由于这个dx dy非常不好统计 我们设这个step为我们从当前x0到范围端点的挪动步数 因为 一组x肯定对应一组y 所以最后我们求一下他们的交集即可

2017.10.22update 被leoly hack一波 我忽略了a==0&&b==0&&c!=0的情况 这种情况应该也是无解直接输出0

#include#include#include#define ll long longusing namespace std;inline int exgcd(int a,int b,long long &x,long long &y){ if (b==0){x=1;y=0;return a;} int tmp=exgcd(b,a%b,x,y); long long t=x;x=y;y=t-a/b*y;return tmp;}int main(){ //freopen("bzoj5027.in","r",stdin); int a,b,c,x1,y1,x2,y2;long long x0=0,y0=0; scanf("%d%d%d%d%d%d%d",&a,&b,&c,&x1,&x2,&y1,&y2);c=-c;if (!a&&!b&&!c){ long long ans=(long long)(x2-x1+1)*(y2-y1+1);printf("%lld",ans);return 0; }if(!a&&!b&&c){printf("0");return 0;} if (a==0){ int tmp=c/b; if (tmp*b==c&&(tmp>=y1)&&(tmp<=y2)) printf("%d",x2-x1+1);else printf("0");return 0; } if (b==0){ int tmp=c/a; if (tmp*a==c&&(tmp>=x1)&&(tmp<=x2)) printf("%d",y2-y1+1);else printf("0");return 0; } int gg=exgcd(a,b,x0,y0);int step1=0,step2=0,step3=0,step4=0;//printf("%lld %lld\n",x0,y0); x0=x0*c/gg;y0=y0*c/gg;//step1: x0->近端点 step2=x0->远端点 //step3:y0->近端点 step4:y0->远端点; int dx=b/gg,dy=-a/gg;if (c%gg) return printf("0"),0; if (dx>0) step1=ceil((double)(x1-x0)/dx),step2=floor((double) (x2-x0)/dx); if (dx<0) step1=ceil((double)(x2-x0)/dx),step2=floor((double) (x1-x0)/dx); if (dy>0) step3=ceil((double)(y1-y0)/dy),step4=floor((double) (y2-y0)/dy); if (dy<0) step3=ceil((double)(y2-y0)/dy),step4=floor((double) (y1-y0)/dy); long long max1=min(step2,step4),min1=max(step1,step3); if (min1>max1) return printf("0"),0; printf("%lld",max1-min1+1); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。