1、noip2017 提高組復賽解題報告 定期推送帳號信息學新聞，競賽自主招生，信息學專業(yè)知識，信息學疑難解答，融科教育信息學競賽培訓等諸多優(yōu)質內容的微信平臺，歡迎分享文章給你的朋友或者朋友圈！以下解題思路及代碼未經(jīng)官方評測，僅供參考，復賽成績以官方（CCF）評測結果為準。 Day1 1.小凱的疑惑 (math.cpp/c/pas)【問題描述】小凱手中有兩種面值的金幣，兩種面值均為正整數(shù)且彼此互素。每種金幣小凱都有無數(shù)個。在不找零的情況下，

2、僅憑這兩種金幣，有些物品他是無法準確支付的?，F(xiàn)在小凱想知道在無法準確支付的物品中，最貴的價值是多少金幣?注意:輸入數(shù)據(jù)保證存在小凱無法準確支付的商品。 【輸入格式】輸入文件名為 math.in。輸入數(shù)據(jù)僅一行，包含兩個正整數(shù) a 和 b，它們之間用一個空格隔開，表示小凱手中金幣的面值。 【輸出格式】輸出文件名為 math.out。輸出文件僅一行，一個正整數(shù) N，表示不找零的情況下，小凱用手中的金幣不能準確支付的最貴的物品的價值。 【輸入

3、輸出樣例 1】math.in3 7 math.out11 【數(shù)據(jù)規(guī)模與約定】 對于 30%的數(shù)據(jù): 1 ≤ a， b ≤ 50。對于 60%的數(shù)據(jù): 1 ≤ a，b ≤ 10,000。對于 100%的數(shù)據(jù):1 ≤ a，b ≤ 1,000,000,000。 數(shù)學太差只找規(guī)律吧。寫英文字母“O”表示通常意義下“Θ” 的概念。 【輸入格式】輸入文件名為 complexity.in。 輸入文件第一行一個正整數(shù) t，表示有 t(t ≤ 10)個

4、程序需要計算時間復雜度。每個程序我們只需抽取其中 “F i x y”和“E”即可計算時間復雜度。注意:循環(huán)結構允許嵌套。 接下來每個程序的第一行包含一個正整數(shù) L 和一個字符串，L 代表程序行數(shù)，字符串表示這個程序的復雜度， “O(1)”表示常數(shù)復雜度， “O(n^w)”表示復雜度為 n^w，其中 w 是一個小于 100 的正整數(shù)(輸入中不包含引號)，輸入保證復雜度只有 O(1)和 O(n^w) 兩種類型。接下來 L 行代表程序中循環(huán)結

5、構中的“F i x y”或者 “E” 。程序行若以“F”開頭，表示進入一個循環(huán)，之后有空格分離的三個字符(串)i x y，其中 i 是一個小寫字母(保證不為 “n” )， 表示新建的變量名， x 和 y 可能是正整數(shù)或 n ，已知若為正整數(shù)則一定小于 100。程序行若以“E”開頭，則表示循環(huán)體結束。 【輸出格式】輸出文件名為 complexity.out。輸出文件共 t 行，對應輸入的 t 個程序，每行輸出“Yes”或“No”或者“ER