澳门新蒲京娱乐


创造透明窗体
澳门新蒲京娱乐 5
Ubuntu系统下搭建Python开发环境澳门新蒲京娱乐:

欧几里德

HDU 2669 Romantic,hdu2669romantic

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

图片 1

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 }

 

2669 Romantic,hdu2669romantic Time Limit:
2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6409Accepted Submission(s): 2667 Problem
De…

Romantic

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

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

题意很轻松便是 a * x + b * y = 1 留神的是X必需大于0 SO… a*(x+b) +
b*(y-a) = a*x + a*b + b*y – a*b = 1

#include<stdio.h>
#define LL __int64


void exgcd(LL a,LL b,LL& d,LL& x,LL& y)
{
    if(!b)d=a,x=1,y=0;
    else
    {
        exgcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}
int main()
{
    LL a,b;
    while(scanf("%I64d%I64d",&a,&b)!=EOF)
    {
        LL d,x,y;
        exgcd(a,b,d,x,y);
        if(d==1)
        {
            while(x<0)
            {
                //a * x + b * y = 1
                //->  a*(x+b) + b*(y-a) = a*x + a*b + b*y - a*b = 1
                x = x+b;
                y = y-a;
            }
            printf("%I64d %I64d\n",x,y);
        }
        else
            printf("sorry\n");
    }
    return 0;
}

相关文章

No Comments, Be The First!
近期评论
    功能
    网站地图xml地图