f(1)=1  f(2x)=f(x)  f(2x+1)=f(x)+f(x+1) 给出n<=10^6，求:所有的i满足f(i)=n

第一道类欧算法

我们考虑一个性质 f(2x+1)=f(x)+f(x+1)=f(2x)+f(2x+2)

所以，显然有f(2x+1)>f(2x) f(2x+1)>f(2x+2)

那么现在我们知道了f(2x+1),自然考虑枚举一个f(2x)

可以按照以下形式转移:f(2x+1),f(2x)->f(x+1),f(x) （f(x+1)=f(2x+1)-f(2x)）

发现转以后的两者也是相邻的，但是不知道奇偶性，较大的那个肯定是基数

那么就可以进行辗转相减，边界就是f(x+1)=f(x)=1

注意这里可以借鉴辗转相除的方法，不然会Tle

#pragma GCC optimize("O3")#pragma G++ optimize("O3")#include
    
     #include
     
      #include
      
       #include
       
        #define LL long long #define M 998244353using namespace std;vector
        
          A; int p[1000010];LL gcd(LL x,LL y,LL& a,LL& b){	if(x==y) return x>1?0:b=((a&=0)+=1)++;	if(x>y){		if(!gcd(--x%y+1,y,a,b)) return 0;		b=b*p[x/y]%M; a=(b+1)%M; return 1;	} else {		if(!gcd(x,--y%x+1,a,b)) return 0;		a=a*p[y/x]%M; b=(a-1+M)%M; return 1;	}}int main(){	freopen("func.in","r",stdin); freopen("func.out","w",stdout);	LL n; scanf("%lld",&n); p[0]=1;	for(int i=1;i<=n;++i) p[i]=(p[i-1]<<1)%M;	for(LL x,y,i=1;i<=n;++i){		if(gcd(n,i,x,y)) A.push_back(x);		if(x<0) printf("%d %d\n",x,i);	}	sort(A.begin(),A.end());	for(LL i=0;i