本人看了代码，时间复杂度能过

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int mon[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
ll cal(ll x) {
	int year=-4712;
	if(x<year) return 0;//保险
	ll res=(x-year+1)*365;
	if(x<1582){
		res+=(x-year)/4+1;
	}else{
		res-=10;//1582年少了10天
		res+=(1581-year)/4+1;
		res+=(x-1580)/4-(x-1500)/100+(x-1200)/400;
	}
	return res;
}
bool check(int x){
	if(x>1582) return x%4==0&&(x%100!=0||x%400==0);//格里高利历
	else return x%4==0;//儒略历
}
int main(){
	int q;
	cin>>q;
	while(q--){
		ll r;
		scanf("%lld",&r);
		++r;//因为是从1月1日向后推r天，不含1月1日，所以++方便处理
		if(r<31){
			printf("%lld 1 4713 BC\n",r);
		}else if(r<366){
			int m=1;
			++mon[2];
			int i=1;
			while(r>mon[i]){
				r-=mon[i];
				++m;
				++i;
			}
			printf("%lld %d 4713 BC\n",r,m);
			--mon[2];//保险
		}else{
			int left=-4712,right=1e9+5;
//left:-x表示公元前x+1年，x表示公元x年（0表示公元前1年） right:确保答案年数不超过1e9
			while(left<right){ //二分查找年
				int mid=(left+right)/2;
				if(cal(mid)>=r) right=mid;
				else left=mid+1;
			}
			r-=cal(left-1);//减去从公元前4713年1月1日到答案年份前一年的天数（年处理完毕）
			if(check(left)) mon[2]=29;
			else mon[2]=28;
			if(left==1582) mon[10]=21;
			else mon[10]=31;
			int m=1,i=1;
			while(r>mon[i]){//找出月份
				r-=mon[i];
				++m;
				++i;
			}//月处理完毕，剩下的r即为天数（因为之前把r加1了）
			if(left==1582&&m==10){
				if(r>=5) r+=10;//1582年少了10天（1582.10.5-1582.10.4)
				printf("%lld %d %d\n",r,m,left);
			}else{
				if(left>0) printf("%lld %d %d\n",r,m,left); //公元
				else printf("%lld %d %d BC\n",r,m,-left+1); //公元前
			}
		}
	}
}