- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
int NOD(int a,int b)
{
if(a==0)
{
return b;
}
if(b==0)
{
return a;
}
if(a==b)
{
return a;
}
if((a%2==0)&&(b%2==0))
{
return 2*NOD(a/2,b/2);
}
else if((a%2==0)&&(b%2!=0))
{
return NOD(a/2,b);
}
else if((a%2!=0)&&(b%2==0))
{
return NOD(a,b/2);
}
else if((a%2!=0)&&(b%2!=0))
{
return NOD(b,abs(a-b));
}
else return 1;
/*
1. НОД(0, n) = n; НОД(m, 0) = m; НОД(m, m) = m;
2. НОД(1, n) = 1; НОД(m, 1) = 1;
3. Если m, n чётные, то НОД(m, n) = 2*НОД(m/2, n/2);
4. Если m чётное, n нечётное, то НОД(m, n) = НОД(m/2, n);
5. Если n чётное, m нечётное, то НОД(m, n) = НОД(m, n/2);
6. Если m, n нечётные, то НОД(m, n) = НОД(n, |m - n|).
*/
}