oip2017提高组复赛解题报告
定期推送帐号信息学新闻竞赛自主招生信息学专业知识信息学疑难解答融科教育信息学竞赛培训等诸多优质内容的微信平台欢迎分享文章给你的朋友或者朋友圈以下解题思路及代码未经官方评测仅供参考复赛成绩以官方CCF评测结果为准。
Day1
1小凯的疑惑mathcppcpas【问题描述】小凯手中有两种面值的金币两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下仅凭这两种金币有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中最贵的价值是多少金币注意输入数据保证存在小凯无法准确支付的商品。【输入格式】输入文件名为mathi
。输入数据仅一行包含两个正整数a和b它们之间用一个空格隔开表示小凯手中金币的面值。【输出格式】输出文件名为mathout。输出文件仅一行一个正整数N表示不找零的情况下小凯用手中的金币不能准确支付的最贵的物品的价值。【输入输出样例1】mathi
37mathout11【数据规模与约定】对于30的数据1≤ab≤50。对于60的数据1≤ab≤10000。对于100的数据1≤ab≤1000000000。数学太差只找规律吧。
f设其中一个数为2则2、312、532、752、119得2、
2设其中一个数为3则3、573、7113、11193、1323得3、
2
3设其中一个数为5则5、7235、11395、13475、1763得5、
4
5所以m、
m1
mi
cludeusi
g
amespacestdi
tmai
lo
glo
gam
sca
flldlldm
am1
m
pri
tflldaretur
02时间复杂度complexitycppcpas【问题描述】小明正在学习一种新的编程语言A刚学会循环语句的他激动地写了好多程序并给出了他自己算出的时间复杂度可他的编程老师实在不想一个一个检查小明的程序于是你的机会来啦下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。A语言的循环结构如下其中“Fixy”表示新建变量i变量i不可与未被销毁的变量重名并初始化为x然后判断i和y的大小关系若i小于等于y则进入循环否则不进入。每次循环结束后i都会被修改成i1一旦i大于y终止循环。x和y可以是正整数x和y的大小关系不定或变量
。
是一个表示数据规模的变量在时间复杂度计算中需保留该变量而不能将其视为常数该数远大于100。“E”表示循环体结束。循环体结束时这个循环体新建的变量也被销毁。注本题中为了书写方便在描述复杂度时使用大
f写英文字母“O”表示通常意义下“Θ”的概念。【输入格式】输入文件名为complexityi
。输入文件第一行一个正整数t表示有tt≤10个程序需要计算时r