問題 C: 磨刀

時間限制:?1 Sec??內(nèi)存限制:?128 MB
提交:?190??解決:?39
[提交] [狀態(tài)] [討論版] [命題人:admin]

題目描述

磨刀是一個講究的工作，只能在n℃下進行，所以我們首先要做的就是把刀的表面溫度提升到n℃。
處理刀身溫度有兩種方式：
????1.淬火，使刀身溫度提高a℃；
????2.冰敷，使刀身溫度降低b℃。
寶兒姐想知道，能否經(jīng)過多次處理，使得刀身溫度達到n℃。

輸入

每組輸入包含一行：包含三個非負整數(shù)n, a, b，含義如上文，數(shù)據(jù)范圍均不超過2^63，輸入已EOF結(jié)束?

輸出

根據(jù)計算，輸出“YES”或“NO”。?

樣例輸入

3 6 9

樣例輸出

YES

提示

對于第一個樣例先冰敷使刀身溫度降至-9℃，在淬火使刀身溫度升至3℃即可 。
刀身起始溫度為0 。

?

---

?

大致思路：

　　1、第一眼想到bfs，其實不行，數(shù)據(jù)返回太大，畢竟數(shù)據(jù)范圍均不超過2^63！

　　2、用longlong來存儲所有數(shù)據(jù)！

　　3、本題求的是一個方程式：a*x+b*y=n, x表示a磨刀的次數(shù)，y表示b磨刀的次數(shù)！當(dāng)然了x和y在應(yīng)用擴展歐幾里得算法的時候會出現(xiàn)負值的情況，需要剔除掉這些情況|！

　　4、初始溫度為0，看‘’提示‘’得到的信息！一點瑕疵！

1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<string> 5 #include<algorithm> 6 #define ll long long 7 using namespace std; 8 #define N 100 9 10 ll exgcd(ll a,ll b,ll x,ll y){ 11 if(!b) 12 { 13 x=1;y=0;return a; 14 } 15 else{ 16 17 ll r=exgcd(b,a%b,y,x); 18 y-=a/b*x; 19 return r; 20 } 21 22 } 23 24 int main(){ 25 ll n,a,b; 26 while(scanf("%lld%lld%lld",&n,&a,&b)!=EOF){ 27 ll r, x,y; 28 r=exgcd(a,b,x,y); 29 if(n%r==0&&x>=0&&y>=0) 30 printf("YES\n"); 31 else 32 printf("NO\n"); 33 } 34 35 return 0; 36 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/zhazhaacmer/p/9399506.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的2018/7/31 -zznu-oj -问题 C: 磨刀- 【扩展欧几里得算法的基本应用】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。