传送门

先考虑$F(x)$到底是个什么东西。我们把$x$用二进制表示出来,如果末位是$0$,那把$0$去掉之后$F(x)$的值不变。否则,设$y$为$x$去掉末尾的$1$,则$F(x)=F(y)+F(y+1)$。我们发现对于$x$,$F(x)$和$F(x+1)$对后面都是有影响的,且在$x$末尾添加$0$或$1$后新的$F(x)$和$F(x+1)$是原来的线性组合:

$$ F(2x)=F(x),F(2x+1)=F(x)+F(x+1)\\ F(2x+1)=F(x)+F(x+1),F((2x+1)+1)=F(x+1) $$

我们把往末尾添数字的过程反过来,发现这就是个辗转相减。当$F(x)$和$F(x+1)$确定后,最多只有一个$x$能与之对应。由于奇数$x$一定满足$F(x)\geq F(x+1)$,所以我们可以枚举$F(x+1)$,然后用辗转相除去模拟辗转相减,就能确定所有的奇数$x$了。

#include <bits/stdc++.h>
#define MAXN 1000010
#define LL long long
using namespace std;

const LL P=998244353;

int n;
vector<int> ans;
LL p2[MAXN];

int gao(int y){
    int x=n;
    static int s[MAXN][2];
    int len=0;
    while(x&&y){
        if(x>y && x%y){
            s[++len][0]=x/y;
            s[len][1]=1;
            x%=y;
        }else if(x<y && y%x){
            s[++len][0]=y/x;
            s[len][1]=0;
            y%=x;
        }else{
            if(min(x,y)!=1) return -1;
            if(y>x){
                s[++len][0]=y/x-1;
                s[len][1]=0;
                y=1;
            }
            s[++len][0]=x/y;
            s[len][1]=1;
            x%=y;
        }
    }
    if(x!=0 || y!=1) return -1;
    LL res=0;
    for(int i=len;i>=1;i--){
        res=res*p2[s[i][0]]%P;
        if(s[i][1]) res=(res+p2[s[i][0]]-1)%P;
    }
    return res;
}

int main(){
    scanf("%d",&n);
    if(n==1) puts("1");
    p2[0]=1;
    for(int i=1;i<MAXN;i++) p2[i]=p2[i-1]*2%P;
    for(int i=1;i<n;i++){
        int temp=gao(i);
        if(temp>=0) ans.push_back(temp);
    }
    sort(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++) printf("%d\n",ans[i]);
}