本人看过代码，认为时间复杂度不会超

#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) {//O(1)
	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){//O(1)
	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--){//O(q)
		ll r;
		scanf("%lld",&r);
		++r;//因为是从1月1日向后推r天，不含1月1日，所以++方便处理
		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;
		}//不会超O(30)
		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); //公元前
		}
	}
}