首页 > 其他分享 >CF585C Alice, Bob, Oranges and Apples

CF585C Alice, Bob, Oranges and Apples

时间:2024-07-28 11:50:53浏览次数:14  
标签:begin frac CF585C Alice long pmatrix printf end Bob

感觉和辗转相除相似,考虑证明正确性

设当前 Alice 的橙子、苹果数为 \(a_0,a_1\),Bob 同理,考虑构造状态矩阵
\(\begin{pmatrix} a_0 & b_0\\ a_1 & b_1\\ \end{pmatrix}\),那么初始状态 \(I\) 为
\(\begin{pmatrix} 1 & 0\\ 0 & 1\\ \end{pmatrix}\),那么 \(A\) 操作相当于
\(\times \begin{pmatrix} 1 & 1\\ 0 & 1\\ \end{pmatrix}\),\(A\) 操作相当于
\(\times \begin{pmatrix} 1 & 0\\ 1 & 1\\ \end{pmatrix}\)

设 \(f(M)=\frac{a_0+b_0}{a_1+b_1}\),相当于需要将 \(f(I)\) 变为 \(\frac{x}{y}\),考虑矩阵乘法对 \(I\) 的改变,但是发现并不好做,由于知道最终状态,那么考虑倒序求解,设 \(P\) 为当前状态,且可以拆分为 \(P=AP'\)(下一步状态),若 \(f(P')=\frac{a+b}{c+d}=\frac{n}{m}\),那么 \(f(P)=\frac{a+b+c+d}{c+d}=\frac{n+m}{m}\),相当于 \(f(P)=\frac{n}{m}\),若 \(n>m\),\(f(P')=\frac{n-m}{m}\),否则 \(f(P')=\frac{n}{m-n}\),那么自然地利用辗转相除法求出此次乘上的是 \(A\) 还是 \(B\) 了

#include<bits/stdc++.h>
using namespace std;
long long x,y;
void exgcd(long long a,long long b){
	if(a>b){
		if(b!=1) printf("%lldA",a/b),exgcd(a%b,b);
		else printf("%lldA",a-1);
	}
	else{
		if(a!=1) printf("%lldB",b/a),exgcd(a,b%a);
		else printf("%lldB",b-1);
	}
}
int main(){
    scanf("%lld%lld",&x,&y);
	if(__gcd(x,y)==1) exgcd(x,y);
	else printf("Impossible");
	return 0;
}

标签:begin,frac,CF585C,Alice,long,pmatrix,printf,end,Bob
From: https://www.cnblogs.com/zyxawa/p/18328051

相关文章

  • QComboBox列表设计
    我想自定义QComboBox列表背景。当我悬停时,我需要一个圆角框。我已附上当前图片和我需要的内容。这是我的样式表代码QComboBox{border:1pxsolidblack;background-color:white;font-size:15pt;padding:1px18px1px3px;}QComboBox:......
  • 题解:CodeForces 346A Alice and Bob[博弈/数论]
    CodeForces346AA.AliceandBobtimelimitpertest2secondsmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputItissoboringinthesummerholiday,isn'tit?SoAliceandBobhaveinventedanewgametoplay.Therulesa......
  • WPF ComboBox数据绑定:初始化动态加载ItemsSource后首次赋值Text不显示问题解决
    原来:<ComboBoxText="{BindingItem}"ItemsSource="{BindingItemLists}"></ComboBox>privatevoidParas_Init(){ItemLists=newObservableCollection<string>();ItemLists.Add("111......
  • 学懂C#编程:WPF应用开发系列——WPF之ComboBox控件的详细用法
    WPF(WindowsPresentationFoundation)中的ComboBox控件是一个下拉列表控件,允许用户从一组预定义的选项中选择一个选项。以下是ComboBox控件的详细用法,并附带示例说明。ComboBox的基本用法1.XAML定义:在XAML中定义一个ComboBox控件,并添加一些选项。<Windowx:Class="ComboBox......
  • repositoryItemComboBox控件的使用(转)
    DevExpress中的repositoryItemComboBox控件得到索引值和选项值有时候会在界面中使用下拉框,并且这种下拉框的属性为DevExpress.XtraEditors.Repository.RepositoryItemComboBox,这种下拉框该如何得到索引值和选项值呢?添加下拉框选项repositoryItemComboBox1.Items.Add("1");repos......
  • WPF中ComboBox几种数据绑定的方法
    一、用字典给ItemsSource赋值XMAL、<ComboBoxName="cmb_list"Grid.Row="1"Grid.Column="1"Height="23"DisplayMemberPath="Value"SelectedValuePath="Key"SelectionChanged="cmb1_SelectionChanged"......
  • QT 中QcomboBox控件的详细用法
    在Qt中,QComboBox 是一个用于选择下拉列表中的项目的控件。它继承自 QWidget 并提供了许多成员函数来操作和管理这个下拉列表。以下是一些常用的 QComboBox 成员函数及其基本用法:构造函数QComboBox(QWidget*parent=nullptr):创建一个新的 QComboBox 对象,并指定其父......
  • 2024-06-15:用go语言,Alice 和 Bob 在一个环形草地上玩一个回合制游戏。 草地上分布着一
    2024-06-15:用go语言,Alice和Bob在一个环形草地上玩一个回合制游戏。草地上分布着一些鲜花,其中Alice到Bob之间顺时针方向有x朵鲜花,逆时针方向有y朵鲜花。游戏规则如下:1.游戏从Alice开始。2.每个回合中,当前玩家必须选择顺时针或逆时针,并在所选方向上摘取一朵鲜花。......
  • comboBox 下拉框的基础使用
    privatevoidFrmAddStudent_Load(objectsender,EventArgse){StudentClassServerstudentClassServer=newStudentClassServer();List<StudentClass>students=studentClassServer.GetStudentClasses();//获取下拉框的数据//向集合第一个位置插入......
  • PyQT5之QComboBox
    importos.pathfromPyQt5importQtWidgetsfromPyQt5importQtCore,QtGuiimportsysimportcv2classSpinBoxPanel(QtWidgets.QWidget):def__init__(self,*args,**kwargs):super().__init__(*args,**kwargs)select_btn=QtWidgets.QP......