本体有严谨$O(1)$算法，瓶颈在于答案的长度输出，可以应对$1e12$范围内的数据，若加上取模，则理论可达$1e18$的范围

以下是高精度代码（可过1e12）

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int BUF_SIZE=1<<20;
char buf[BUF_SIZE];
int buf_pos=0,buf_len=0;
inline char get_char(){
	if(buf_pos==buf_len){
		buf_len=fread(buf,1,BUF_SIZE,stdin);
		buf_pos=0;
		if(!buf_len) return EOF;
	}
	return buf[buf_pos++];
}
inline int read_ll(){
	int x=0;
	char c=get_char();
	while(c<'0') c=get_char();
	while(c>='0') x=(x<<3)+(x<<1)+(c^48),c=get_char();
	return x;
}
struct BigInt{
	vector<int> d;
	static const int BASE=1e9;
	BigInt(int x=0){ *this=x; }
	BigInt& operator=(int x){
		d.clear();
		if(!x) d.push_back(0);
		while(x) d.push_back(x%BASE),x/=BASE;
		return *this;
	}
	BigInt operator*(int x)const{
		BigInt res;
		res.d.resize(d.size());
		int carry=0;
		for(int i=0;i<(int)d.size();i++){
			int cur=d[i]*x+carry;
			res.d[i]=cur%BASE;
			carry=cur/BASE;
		}
		while(carry) res.d.push_back(carry%BASE),carry/=BASE;
		return res;
	}
	BigInt operator+(int x)const{
		BigInt res=*this;
		int carry=x,i=0;
		while(carry){
			if(i>=(int)res.d.size()) res.d.push_back(0);
			int cur=res.d[i]+carry;
			res.d[i]=cur%BASE;
			carry=cur/BASE;
			i++;
		}
		return res;
	}
	BigInt lshift(int k)const{
		BigInt res=*this;
		while(k>=30) res=res*(1<<30),k-=30;
		if(k>0) res=res*(1<<k);
		return res;
	}
	void print(){
		if(d.empty()){ putchar('0');return; }
		printf("%d",d.back());
		for(int i=(int)d.size()-2;i>=0;i--) printf("%09d",d[i]);
	}
};
signed main(){
	int n=read_ll();
	int K=(int)((sqrtl(8.0L*n+1.0L)-1.0L)/2.0L);
	int TK=K*(K+1)>>1;
	int coeff=n-TK+K-1;
	BigInt ans=BigInt(coeff).lshift(K)+1;
	ans.print();
	return 0;
}

（注：部分模块代码，如超快读，借助AI完成）