nyoj1047欧几里得
生活随笔
收集整理的這篇文章主要介紹了
nyoj1047欧几里得
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
歐幾里得
時間限制：1000?ms ? 描述已知gcd(a,b)表示a,b的最大公約數。
現在給你一個整數n，你的任務是在區間[1,n)里面找到一個最大的x，使得gcd(x,n)等于1。
輸入接下來有T行，每行有一個正整數n (1<=n<=10^1000)。
題目大意： ?在1--n中找一個最大的數x，讓x與n的最大公約數為1
思路： ?很明顯n-1就是需要找的x，比如:n=10，x就是9；n=45，x=44；.....
看到這也許你想動手開始寫程序了(又或者和我思路一樣，代碼已經碼好，可是WrongAnswer)，別急，往下看。
注意：數據范圍?(1<=n<=10^1000)，這個1要特別注意，如果按x=n-1，那此時x=0，明顯錯了，所以1為特殊數據，n=1時，答案應該是1；
10^1000, 足足1000位數，容易想到用字符串存，然后就是-1，輸出，就行了。
再給幾組測試數據：
3
1
1000000000000000000000000
1234567890
輸出
1
999999999999999999999999
1234567889
AC代碼:
總結
以上是生活随笔為你收集整理的nyoj1047欧几里得的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： nyoj496巡回赛-拓扑排序-拓扑序列
- 下一篇： 2020年10月份Github上热门的开