귀속--연습3--noi7592 최대 공약수 구하기 문제

4793 단어

귀속--연습3--noi7592 최대 공약수 구하기 문제


생각


두 가지 저급 오류: 1.ll setMax(ll &m, ll &n)에서 인용이 없습니다. 결과는 값만 전달되고 주소는 전달되지 않았습니다. 2.return f(n,m%n);이 말은 return을 쓰는 것을 잊어버렸다
//결과가 겹겹이 되돌아올 수 있도록 보증하다

제목


7592: 최대 공약수 문제 구하기


총 시간 제한:
1000ms
메모리 제한:
65536kB
묘사
두 개의 정수를 정해 그것들의 최대 공약수를 구하다.
입력
두 개의 정수(<1000000000)를 포함하는 행을 입력합니다.
출력
이 두 정수의 최대 공약수인 정수를 출력합니다.
샘플 입력
6 9

샘플 출력
3

힌트
최대 공약수를 구하려면 전유상제법을 사용할 수 있다.
가령 a>b>0을 가정하면 a와 b의 최대 공약수는 b와 a%b의 최대 공약수와 같다. 그리고 b와 a%b를 새로운 입력으로 한다.
이 과정은 a%b가 0이 될 때까지 계속 줄어들기 때문에 b의 값은 요구하는 최대 공약수이다.
예:
9와 6의 최대 공약수는 6과 9% 6=3의 최대 공약수와 같다.
6%3==0이므로 최대 공약수는 3입니다.

3. AC 코드

 1 /*
 2 noi7592 
 3  4 f(m,n)=f(n,m%n)
 5  
 6 n==0 ,m  
 7 */
 8 /*
 9 10 1. ll setMax(ll &m,ll &n) , , 
11 2. return f(n,m%n);  
12 */ 
13 #include 
14 #include 
15 #define ll long long 
16 using namespace std;
17 // m>n 
18 ll f(ll m,ll n){
19     if(0==n) return m;
20     else{
21         return f(n,m%n);
22     } 
23 }
24 // m>n 
25 ll setMax(ll &m,ll &n){
26     if(n>m){
27         ll temp=n;
28         n=m;
29         m=temp;
30     }
31 } 
32 int main(){
33     //freopen("in.txt","r",stdin);
34     ll m,n;
35     cin>>m>>n;
36     setMax(m,n);
37     ll ans=f(m,n);
38     cout<endl;
39     return 0;
40 } 

좋은 웹페이지 즐겨찾기