2022年CSP-J第二輪真題源碼解析個人解析，非評分標(biāo)準(zhǔn)答案1. T1?[CSP-J?2022]乘方【題目描述】小文同學(xué)剛剛接觸了信息學(xué)競賽，有一天她遇到了這樣一個題：給定正整數(shù)a和 b，求ab的值是多少ab即b個a相乘的值，例如23即為3個2相乘，結(jié)果為2×2×2=8簡單！”小文心想，同時很快就寫出了一份程序，可是測試時卻出現(xiàn)了錯誤小文很快意識到，她的程序里的變量都是 int類型的在大多數(shù)機器上，int類型能表示的最大數(shù)為231-1，因此只要計算結(jié)果超過這個數(shù)，她的程序就會出現(xiàn)錯誤由于小文剛剛學(xué)會編程，她擔(dān)心使用int計算會出現(xiàn)問題因此她希望你在ab的值超過 109時，輸出一個-1進(jìn)行警示，否則就輸出正確的ab的值然而小文還是不知道怎么實現(xiàn)這份程序，因此她想請你幫忙輸入格式】輸入共一行，兩個正整數(shù)a，b輸出格式】輸出共一行，如果ab的值不超過109，則輸出ab的值，否則輸出-1輸入輸出樣例】輸入#110 9輸出#11000000000輸入#223333 66666輸出#2-1【說明/提示】對于10%的數(shù)據(jù)，保證b=1對于30%的數(shù)據(jù)，保證b≤2對于60%的數(shù)據(jù)，保證b≤30，ab≤1018。

對于100%的數(shù)據(jù)，保證1≤a,b≤109參考源碼：1. #include2. using?namespace?std;3. #define?ll?long?long?int4. const?ll?c?=?1e9;5. ll?f(ll?a,?ll?b)?{6. ????ll?ret?=?1;7. ????if?(a==1)?return?1;8. ????for?(ll?i?=?1;?i?<=?b;?i++)?{9. ????????ret?*=?a;10. ????????if?(ret?>?c)?{11. ????????????ret?=?-1;12. ????????????break;13. ????????}14. ????}15. ????return?ret;16. }17. int?main()?{18. ????ll?a,?b;19. ????cin?>>?a?>>?b;20. ????cout?<

但是這題要考查的核心不是時間復(fù)雜度，而是參數(shù)范圍和返回值的范圍問題（題目中已經(jīng)提示了）先分析一下題目會不會出現(xiàn)TLE(Time Limit Exceeded)問題ab的值不超過109，int型變量的最大值為231-1（231-1>109），也就是說當(dāng)a≥2，最多循環(huán)32次就超過了int型的范圍，當(dāng)然也超過了109范圍所以無需考慮時間復(fù)雜度，自然也就不需要采用快速冪算法下面討論越界問題可以在每次累乘的時間判斷結(jié)果是否大于109，大于則返回-1，結(jié)束循環(huán)這里面有一個問題需要考慮：假設(shè)n次累乘的結(jié)果小于109，n+1次累乘的結(jié)果大概在什么范圍內(nèi)？由于a≤109，n+1次累乘的結(jié)果（中間結(jié)果）有可能int越界，但是不可能long long int越界(109×109)，所以需要將相關(guān)的變量設(shè)置為long long int，而不能用int型，防止出現(xiàn)整數(shù)上溢出問題在上面程序中，將(a,b,ret)三個變量設(shè)置為long long int，至于為什么要將a和b也設(shè)置為long long int（b可以不設(shè)置），具體案例可看下面測試代碼：1. #include?2. using?namespace?std;3. int?main(){4. ????long?long?int?a=1e+9;5. ????long?long?int?b=1e+9;6. ????//不溢出7. ????cout<

左邊計算結(jié)果的范圍取決于a和b的最大范圍，例如上例中a為long long int，b為int，則計算結(jié)果的最大范圍就是long long int；如果計算結(jié)果沒有溢出，但是計算結(jié)果不在c的范圍之內(nèi)，也可能溢出，例如上例中ret1為int一個誤區(qū)就是計算結(jié)果不存儲就不會溢出，上面例子已經(jīng)給出（cout直接輸出或者直接判斷大小等）在本題中a=1需要單獨枚舉來計算，直接返回1；本題中的b的范圍實際上不需要考慮運行截圖：測試用例1測試用例2測試用例3測試用例42. T2?[CSP-J 2022] 解密【題目描述】給定一個正整數(shù)k，有k次詢問，每次給定三個正整數(shù)ni、ei、di，求兩個正整數(shù)pi、qi，使ni=pi×qi、ei×di=(pi - 1)(qi - 1) + 1輸入格式】第一行一個正整數(shù)k，表示有k次詢問接下來k行，第i行三個正整數(shù)ni、ei、di輸出格式】輸出k行，每行兩個正整數(shù)pi，qi表示答案為使輸出統(tǒng)一，你應(yīng)當(dāng)保證pi<=qi如果無解，請輸出NO輸入輸出樣例】輸入#110770 77 5633 1 211545 1 499683 3 227858 3 257723 37 13572 26 11867 17 17829 3 263528 4 109輸出#12 385NONONO11 783 2412 286NONO6 88【數(shù)據(jù)范圍】以下記m=n-e×d+2。

保證對于100%的數(shù)據(jù)，1≤k≤105，對于任意的1≤i≤k，1≤ni≤1018，1≤ei×di≤1018，1≤m≤109參考源碼1：1. #include?2. #include?3. using?namespace?std;4. #define?ll?long?long?int5. int?main()?{6. ???ll?k,n,e,d,m;7. ???ll?p,q;8. ???ll?temp1,temp2,root;9. ???cin>>k;10. ???for(ll?i=1;i<=k;i++){11. ???????cin>>n>>e>>d;12. ???????m=n-e*d+2;13. ?????temp1=m*m-4*n;14. ?????root=sqrt(temp1);15. ?????if?(root*root!=temp1){16. ?????????cout<<"NO"<

由p+q=m,pq=n可以推到出p=m-m2-4n2,q=m-p題目要求是p<=q在計算p的公式中，m2-4n≥0，在程序中不需要進(jìn)行判斷在程序中需要判斷兩個點：（1）m2-4n能否有完全平方根；（2）m-m2-4n能否被2整除運行截圖1：測試用例1測試用例2參考源碼2：1. #include2. using?namespace?std;3. #define?ll?long?long?int4. int?main()?{5. ????ll?k,?n,?e,?d,?m;6. ????ll?p,?q;7. ????cin?>>?k;8. ????for?(ll?i?=?1;?i?<=?k;?i++)?{9. ????????cin?>>?n?>>?e?>>?d;10. ????????m?=?n?-?e?*?d?+?2;11. ????????ll?begin?=?1,?end?=?m?/?2;12. ????????ll?area;13. ????????while?(begin?<=?end)?{14. ????????????p?=?(begin?+?end)?/?2;15. ????????????q?=?m?-?p;16. ????????????area?=?p?*?q;17. ????????????if?(area??n)?{20. ????????????????end?=?p?-?1;21. ????????????}?else?{22. ????????????????cout?<?end)?{27. ????????????cout?<

由于p<=q，p的二分區(qū)間是1,m2，判斷條件是pq是否大于、等于或者小于n能采用二分法的原因是：根據(jù)p+q=m,pq=n，可以推導(dǎo)出-p-m22+m24=n，n與p是之間的關(guān)系是單調(diào)遞減上述算法一次計算的時間復(fù)雜度是olog2m2=olog2m-1可以簡單估最大計算次數(shù)，由于m的最大值為109，32位2進(jìn)制最多能表示232個數(shù)，232大于109，因此最大計算次數(shù)是不會超過31次下面分析暴力算法存在的問題由于pq=n，因此可以將暴力算法的枚舉次數(shù)優(yōu)化為n，用p+q=m對每次枚舉進(jìn)行判斷n的最大值為1018，所以一次計算的最大次數(shù)為109，這就會出現(xiàn)TLE問題暴力算法的源碼如下：1. #include2. using?namespace?std;3. #define?ll?lon。