#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
#define MAX 1000000
using namespace std;
char In[100000];
ll fm[40][MAX];
ll N,l,k,L,R,answer,q,mid;
ll alpha(ll x)
{
	ll t=1;
	while(t<<1<=x)t<<=1;
	return t;
}
ll f(ll a,ll b)
{
	return (a+1)%b+b;
}
ll F(ll n,ll m)
{
	ll ans;
	if(m<MAX)
		if(fm[n][m])
			return fm[n][m];
	if(m==0)ans=n;
	else ans=f(F(n,m-alpha(m)),alpha(m)*l);
	if(m<MAX)fm[n][m]=ans;
	return ans;
}
int main()
{
	
	scanf("%s%lld",In,&N);
	N-=1;
	l=strlen(In);
	for(int i=0;i<l;i++)
	{
		L=0;
		R=N;
		while(L<=R)
		{
			mid=(L+R)>>1;
			q=F(i,mid);
			if(N>=q)answer=q,L=mid+1;
				else R=mid-1;
		}
		if(answer==N)
		{
			printf("%c",In[i]);
			return 0;
		}
	}
 } 

大致思路是求出原串第n个字符出现第m次的位置(m,n从零开始)的表达式$F(n,m)$

用二分找$F(n,m)=N$的解$n_0,m_0$,输出第$n_0$个字符，但在输入ABC 1000时求不出解（亲测二分没问题），有大佬能帮忙解释一下吗？