月赛T2,hack我自己
  • 板块学术版
  • 楼主InterN_NOT_FOUND
  • 当前回复18
  • 已保存回复18
  • 发布时间2024/10/2 18:30
  • 上次更新2024/10/2 20:19:08
查看原帖
月赛T2,hack我自己
479532
InterN_NOT_FOUND楼主2024/10/2 18:30

rt,code:

#include<bits/stdc++.h>

namespace INstd {
	std::string Set_Nsolution = "-1";
	#define int __int128
	#define NO_SOLUTION {cout << Set_Nsolution;return 0;}

	namespace mathematicsh{
		inline int gcd(int a,int b){
			return (b==0?a:gcd(b,a%b));
		}
	}

	namespace IO{
		inline bool isnum(char ch){return ch>='0'&&ch<='9';}
		inline int read()
		{
			int x=0,f=1;char ch=getchar();
			while (!isnum(ch)){if (ch=='-') f=-1;ch=getchar();}
			while (isnum(ch)){x=x*10+ch-48;ch=getchar();}
			return x*f;
		}
		inline void out(int x,char ch){
		    if(x<0){putchar('-');x=-x;}
		    if(x>9)out(x/10,'/');
		    putchar(x%10+'0');
		    if(ch=='l')putchar('\n');
		    if(ch=='s')putchar(' ');
		}
	}

	namespace Debug{
		#define err() cout<<"err "<<__LINE__<<endl,exit(0)
		#define pot(args...) \
		GPT(#args),cout<<"  Line "<<__LINE__<<"\t: ", \
		PPT(args),cout<<"\n\n"
		void PPT(){}
		template<typename TYPE,typename... TYPES>
		void PPT(const TYPE& x,const TYPES&... y){
		    std::cout<<x<<' ';
		    PPT(y...);
		}
		void GPT(std::string nam){std::cout<<std::setw(29)<<nam;}
	}

	using namespace std;
	using namespace mathematicsh;
	using namespace IO;
	using namespace Debug;
}

using namespace INstd;

const int mx = 4e8, prm1 = 399999959, prm2 = 399999949;

int T = read();

inline int Exgcd (int a, int b, int &x, int &y) {
	if (!b) {
    	x = 1;
    	y = 0;
   		return a;
  	}
 	int d = Exgcd(b, a % b, x, y);
  	int t = x;
  	x = y;
  	y = t - (a / b) * y;
  	return d;
}

signed main()
{
	fflush(stdout);
	while (T --) {
		int x, y;
		printf("? "); out(prm1, 'l');
		fflush(stdout);
		x = read();
		fflush(stdout);
		
		printf("? "); out(prm2, 'l');
		fflush(stdout);
		y = read();
		fflush(stdout);
		
		if (x == y) {
			printf("! "); out(x, 'l');
			fflush(stdout);
			continue;
		}
		
		int xx = 0, yy = 0;
		Exgcd(prm1, prm2, xx, yy);
		xx *= (y - x); yy *= -(y - x);
		int k1, k2;
		
		k1 = (xx > 0 && xx % prm2 != 0) ? xx % prm2 : xx % prm2 + prm2;
		k2 = (yy > 0 && yy % prm1 != 0) ? yy % prm1 : yy % prm1 + prm1;
		
		int ans1 = k1 * prm1 + x, ans2 = k2 * prm2 + y;
		
		printf("! "); 
		
		if (ans1 % prm1 == x && ans2 % prm2 == y)
			out(ans1, 'l');
		else out(ans2, 'l');
		
		fflush(stdout);
	}
	return 0;
}

思路就是弄两坨大质数跑扩欧,但是我在测试手造样例时发现一个问题

我假设 m=399999958m=399999958 ,运行过程:

1
? 399999959
399999958
? 399999949
9
! 159999963600002049

而且还AC了,求问

2024/10/2 18:30
加载中...