10pts(AC on #3) exgcd求调
查看原帖
10pts(AC on #3) exgcd求调
1284081
haoran150楼主2025/7/24 19:32

#9,10TLE,其余WA

#include<bits/stdc++.h>
using namespace std;
#define int long long
int T,a,b,c,minx,miny,maxx,maxy,cnt,x,y;
#define LOCAL
namespace ly
{
    namespace IO
    {
        #ifndef LOCAL
            #define SIZE (1<<20)
            char in[SIZE],out[SIZE],*p1=in,*p2=in,*p3=out;
            #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,SIZE,stdin),p1==p2)?EOF:*p1++)
            #define flush() (fwrite(p3=out,1,SIZE,stdout))
            #define putchar(ch) (p3==out+SIZE&&flush(),*p3++=(ch))
            class Flush{public:~Flush(){flush();}}_;
        #endif
        template<typename type>
        inline void read(type &x)
        {
            x=0;bool flag(0);char ch=getchar();
            while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
            while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
            flag?x=-x:0;
        }
        template<typename type>
        inline void write(type x,bool flag=0)
        {
            x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
            do Stack[++top]=x%10,x/=10;while(x);
            while(top) putchar(Stack[top--]|48);
            flag?putchar('\n'):putchar(' ');
        }
        #ifndef LOCAL
            #undef SIZE
            #undef getchar
            #undef putchar
            #undef flush
        #endif
    }
}using namespace ly::IO;
int exgcd(int a,int b){
  if(b==0){
    x=1,y=0;
    return a;
  }
  int d=exgcd(b,a%b),temp=x;
  x=y;
  y=temp-a/b*y;
  return d;
}
signed main(){
	read(T);
	while(T--){
		minx=miny=INT_MAX;
		maxx=maxy=INT_MIN;
		cnt=0;
		read(a),read(b),read(c);
		
		int gcd=__gcd(a,b);
//		printf("%d and %d gcd:%d\n",a,b,gcd);
//		printf("ans:");
		if(c%gcd){
			puts("-1");
			continue;
		}
		exgcd(a,b);
		x=x*c/gcd,y=y*c/gcd;
//		auto ex_gcd = exgcd(a,b);
//		int x = ex_gcd.first,y = ex_gcd.second;
//		printf("special answer:[%d,%d]\n",x,y);
//		printf("normal answer:[%d+%dk,%d-%dk]\n",x,(b/gcd),y,(a/gcd));
		int maxk=y*gcd/a,mink=-x*gcd/b;
//		printf("round k:from %.2lf to %.2lf\n",-x*1.0*gcd/b,y*1.0*gcd/a);
		if(maxk<=mink){//无正整数解 
			for(int i=maxk-1;i<=mink+1;i++){
				int nx=x+i*(b/gcd),ny=y-i*(a/gcd);
				if(nx>0) minx=min(minx,nx);
				if(ny>0) miny=min(miny,ny);
			}
			write(minx),write(miny);
//			printf("%d %d",minx,miny);
		}
		else{
			for(int i=mink-1;i<=maxk+1;i++){
				int nx=x+i*(b/gcd),ny=y-i*(a/gcd);
				if(nx>0&&ny>0){
					cnt++; 
					minx=min(minx,nx);
					maxx=max(maxx,nx);
					miny=min(miny,ny);
					maxy=max(maxy,ny);
				}
//				printf("x:%d y:%d\n",nx,ny);
			}
			write(cnt);
			write(minx),write(miny),write(maxx),write(maxy);
//			printf("%d %d %d %d %d",cnt,minx,miny,maxx,maxy);
		}
		puts("");
	}
}

样例和这里的Hack都过了,找不到问题了QAQ.
死亡记录
玄关求条! @meifan666

2025/7/24 19:32
加载中...