HDU 2669 Romantic

2018-06-17 22:20:37来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6409    Accepted Submission(s): 2667


Problem Description
The Sky is Sprite.
The Birds is Fly in the Sky.
The Wind is Wonderful.
Blew Throw the Trees
Trees are Shaking, Leaves are Falling.
Lovers Walk passing, and so are You.
................................Write in English class by yifenfei



Girls are clever and bright. In HDU every girl like math. Every girl like to solve math problem!
Now tell you two nonnegative integer a and b. Find the nonnegative integer X and integer Y to satisfy X*a + Y*b = 1. If no such answer print "sorry" instead.
 

 

Input
The input contains multiple test cases.
Each case two nonnegative integer a,b (0<a, b<=2^31)
 

 

Output
output nonnegative integer X and integer Y, if there are more answers than the X smaller one will be choosed. If no answer put "sorry" instead.
 

 

Sample Input
77 51 10 44 34 79
 

 

Sample Output
2 -3 sorry 7 -3
 

 

Author
yifenfei
 

 

Source
HDU女生专场公开赛——谁说女子不如男
 
 

 

Recommend
lcy   |   We have carefully selected several similar problems for you:  2668 2674 2671 2670 2672 
 
裸的扩展欧几里得
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define lli long long int 
 7 using namespace std;
 8 void read(lli &n)
 9 {
10     char c='+';lli x=0;bool flag=0;
11     while(c<'0'||c>'9')
12     {c=getchar();if(c=='-')flag=1;}
13     while(c>='0'&&c<='9')
14     {x=x*10+(c-48);c=getchar();}
15     flag==1?n=-x:n=x;
16 }
17 lli x,y;
18 lli exgcd(lli a,lli b,lli & x,lli & y)
19 {
20     if(b==0)
21     {
22         x=1;y=0;
23         return a;
24     }
25     lli r=exgcd(b,a%b,y,x);
26     y-=a/b*x;
27     return r;
28 }
29 int main()
30 {
31     lli a,b;
32     while(scanf("%lld%lld",&a,&b)==2)
33     {
34         lli d=exgcd(a,b,x,y);
35         if(1%d!=0)
36             printf("sorry\n");
37         else if(d==-1)
38             printf("sorry\n");
39           else 
40         {
41             x*=1/d;
42               b=fabs(b);
43               b=b/d;
44             lli ans=x%b;
45             if(ans<=0)
46                 ans+=b;
47             printf("%lld %lld\n",ans,(1-a*ans)/b);        
48         }
49     }
50     
51     return 0;
52 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:15. 3Sum

下一篇:boost::accumulators 用法学习