题目描述

现在给你两个变量 x和y。x和y的初值都是1.
你每次可以选择 x=x+y;运行一次，也可以选择 y=x+y运行一次。
给定一个整数N，问你最少经过几次加等运算，可以让x变量里存着整数N，y变量的值可以随意。每次操作以赋值号左边的变量命名。
当然，操作步骤可能有很多种方法，你必须输出字典序最小的方案。
比如3.你可以执行一次 y=x+y; 再执行一次 x=x+y; 这样输出方案是 YX.
你也可以执行两次 x=x+y; 这样输出方案是XX.
当然字典序最小的是 XX

输入格式 Input Format

一个整数N。表示加法要得到的结果。
20%数据保证，N<=100
50%的数据保证，N<=10000
100%的数据保证，2<=N<=1000000

输出格式 Output Format

一个字符串，表示字典序最小的输出方案。

输入：

10

输出：

XXYYX

---

想法

设最后x=n，y=t，
呢么前n/t步操作肯定是X操作，
前n/t步之前的状态就是x=n%t , y=t,
我们已知最初x=1 y=1;
且X,Y操作也就是辗转相除的过程。

枚举y的值然后模拟辗转相除记录过程即可。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
string s1,s2;
inline int gcd(int a,int b)
{
	if(b==1&&a==1)
		return 1;
	if(b<1||a<1)
		return 0;
	if(a>=b)
	{
		s1+='X';
		return gcd(a-b,b);
	}
	else
	{
		s1+='Y';
		return gcd(a,b-a);
	}
	return 0;
}
int main()
{
	s2+="YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY";
	int x,y,n,k;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		if(n%i==0)
			continue;
		x=n%i;
		for(int j=1;j<=n/i;j++)
			s1+='X';
		y=i;
		if(gcd(x,y)==1)
		{
			if(s1.size()<s2.size())
			{
				s2.clear();
				s2+=s1;
			}
			else
			{
				if(s1.size()==s2.size())
				{
					k=0;
					for(int j=s1.size()-1;j>=0;j--)
					{
						if(s1[j]=='X'&&s2[j]=='Y')
						{
							k=1;
							break;
						}
						if(s1[j]=='Y'&&s2[j]=='X')
						{
							break;
						}
					}
					if(k==1)
					{
						//cout<<i<<endl;
						s2.clear();
						s2+=s1;
					}
				}
			}
			//cout<<s1<<' '<<i<<endl;
		}
		s1.clear();
		//cout<<i<<endl;
	}
	for(int i=s2.size()-1;i>=0;i--)
		cout<<s2[i];
	cout<<endl;
	return 0;
}