2018/7/31 -zznu-oj -问题 C: 磨刀- 【扩展欧几里得算法的基本应用】

问题 C: 磨刀

时间限制: 1 Sec  内存限制: 128 MB
提交: 190  解决: 39
[提交] [状态] [讨论版] [命题人:admin]

题目描述

磨刀是一个讲究的工作，只能在n℃下进行，所以我们首先要做的就是把刀的表面温度提升到n℃。
处理刀身温度有两种方式：
    1.淬火，使刀身温度提高a℃；
    2.冰敷，使刀身温度降低b℃。
宝儿姐想知道，能否经过多次处理，使得刀身温度达到n℃。

输入

每组输入包含一行：包含三个非负整数n, a, b，含义如上文，数据范围均不超过2^63，输入已EOF结束 

输出

根据计算，输出“YES”或“NO”。 

样例输入

3 6 9

样例输出

YES

提示

对于第一个样例先冰敷使刀身温度降至-9℃，在淬火使刀身温度升至3℃即可 。
刀身起始温度为0 。

---

大致思路：

　　1、第一眼想到bfs，其实不行，数据返回太大，毕竟数据范围均不超过2^63！

　　2、用longlong来存储所有数据！

　　3、本题求的是一个方程式：a*x+b*y=n, x表示a磨刀的次数，y表示b磨刀的次数！当然了x和y在应用扩展欧几里得算法的时候会出现负值的情况，需要剔除掉这些情况|！

　　4、初始温度为0，看‘’提示‘’得到的信息！一点瑕疵！

 #include<iostream>

 #include<stdio.h>

 #include<string.h>

 #include<string>

 #include<algorithm>

 #define ll long long

 using namespace std;

 #define N 100

 ll exgcd(ll a,ll b,ll x,ll y){

     if(!b)

     {

         x=;y=;return a;

     }

     else{

         ll r=exgcd(b,a%b,y,x);

         y-=a/b*x;

         return r;

     }

 }

 int main(){

     ll n,a,b;

     while(scanf("%lld%lld%lld",&n,&a,&b)!=EOF){

         ll r, x,y;

         r=exgcd(a,b,x,y);

         if(n%r==&&x>=&&y>=)

             printf("YES\n");

         else

             printf("NO\n");

     }

     return ;

 }