Join 60,000+ competitive exam aspirants
рдХрд┐рдиреНрд╣реАрдВ рджреЛ рднрд┐рдиреНрди рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХрд╛ рдорд╣рддреНрддрдо рд╕рдорд╛рдкрд╡рд░реНрддрдХ (HCF) рд╣реЛрддрд╛ рд╣реИ:
0
3
1
2
1
рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЗ рдХреЗрд╡рд▓ рджреЛ рдЧреБрдгрдирдЦрдВрдб рд╣реЛрддреЗ рд╣реИрдВ: 1 рдФрд░ рд╕реНрд╡рдпрдВ рд╡реЗ рд╕рдВрдЦреНрдпрд╛рдПрдБред рдЪреВрдВрдХрд┐ рд╡реЗ рднрд┐рдиреНрди рд╣реИрдВ, рдЗрд╕рд▓рд┐рдП рдЙрдирдореЗрдВ 1 рдХреЗ рдЕрд▓рд╛рд╡рд╛ рдХреЛрдИ рдЕрдиреНрдп рдЙрднрдпрдирд┐рд╖реНрда рдЧреБрдгрдирдЦрдВрдб рдирд╣реАрдВ рд╣реЛрддрд╛ рд╣реИред рдЕрддрдГ, рдЙрдирдХрд╛ HCF рд╣рдореЗрд╢рд╛ 1 рд╣реЛрддрд╛ рд╣реИред
рджреЛ рднрд┐рдиреНрди рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдПрдБред
HCF(p1тАЛ,p2тАЛ)=1┬ардЬрд╣рд╛рдБ┬аp1тАЛ,p2тАЛ┬арднрд┐рдиреНрди┬ардЕрднрд╛рдЬреНрдп┬ард╕рдВрдЦреНрдпрд╛рдПрдБ┬ард╣реИрдВ
рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЗ рдХреЗрд╡рд▓ рджреЛ рдЧреБрдгрдирдЦрдВрдб рд╣реЛрддреЗ рд╣реИрдВ: 1 рдФрд░ рд╕реНрд╡рдпрдВ рд╡реЗ рд╕рдВрдЦреНрдпрд╛рдПрдБред рдЪреВрдВрдХрд┐ рд╡реЗ рднрд┐рдиреНрди рд╣реИрдВ, рдЗрд╕рд▓рд┐рдП рдЙрдирдореЗрдВ 1 рдХреЗ рдЕрд▓рд╛рд╡рд╛ рдХреЛрдИ рдЕрдиреНрдп рдЙрднрдпрдирд┐рд╖реНрда рдЧреБрдгрдирдЦрдВрдб рдирд╣реАрдВ рд╣реЛрддрд╛ рд╣реИред рдЕрддрдГ, рдЙрдирдХрд╛ HCF рд╣рдореЗрд╢рд╛ 1 рд╣реЛрддрд╛ рд╣реИред
рдХрдИ рдЫрд╛рддреНрд░ рдЧрд▓рддреА рд╕реЗ рд╕реЛрдЪрддреЗ рд╣реИрдВ рдХрд┐ рдЙрдирдХрд╛ рдХреЛрдИ рдЙрднрдпрдирд┐рд╖реНрда рдЧреБрдгрдирдЦрдВрдб рдирд╣реАрдВ рд╣реИ рдФрд░ 0 рдЪреБрди рд▓реЗрддреЗ рд╣реИрдВ, рд▓реЗрдХрд┐рди 1 рдкреНрд░рддреНрдпреЗрдХ рдкреВрд░реНрдгрд╛рдВрдХ рдХрд╛ рдПрдХ рдЧреБрдгрдирдЦрдВрдб рд╣реИред
рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреА рдкрд░рд┐рднрд╛рд╖рд╛
рдПрдХ рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛ 1 рд╕реЗ рдмрдбрд╝реА рд╡рд╣ рдкреНрд░рд╛рдХреГрддрд┐рдХ рд╕рдВрдЦреНрдпрд╛ рд╣реИ рдЬрд┐рд╕рдХреЗ рдареАрдХ рджреЛ рднрд┐рдиреНрди рдзрдирд╛рддреНрдордХ рд╡рд┐рднрд╛рдЬрдХ рд╣реЛрддреЗ рд╣реИрдВ: 1 рдФрд░ рд╕реНрд╡рдпрдВ рд╡рд╣ рд╕рдВрдЦреНрдпрд╛ред
pтИИPтЯ╣divisors(p)={1,p}
рдЙрднрдпрдирд┐рд╖реНрда рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдХреА рдкрд╣рдЪрд╛рди
рдХрд┐рдиреНрд╣реАрдВ рджреЛ рднрд┐рдиреНрди рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдУрдВ p1тАЛ рдФрд░ p2тАЛ рдХреЗ рд▓рд┐рдП, рдЙрдирдХреЗ рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдХреЗ рд╕рдореБрдЪреНрдЪрдп 1,p1тАЛ рдФрд░ 1,p2тАЛ рд╣реИрдВред рдЗрди рд╕рдореБрдЪреНрдЪрдпреЛрдВ рдХрд╛ рдкреНрд░рддрд┐рдЪреНрдЫреЗрджрди рдЙрднрдпрдирд┐рд╖реНрда рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдХрд╛ рд╕рдореБрдЪреНрдЪрдп рд╣реИред
{1,p1тАЛ}тИй{1,p2тАЛ}={1}
рдорд╣рддреНрддрдо рд╕рдорд╛рдкрд╡рд░реНрддрдХ (HCF) рдЬреНрдЮрд╛рдд рдХрд░рдирд╛
рдЙрднрдпрдирд┐рд╖реНрда рдЧреБрдгрдирдЦрдВрдбреЛрдВ рдХреЗ рд╕рдореБрдЪреНрдЪрдп 1 рдореЗрдВ рд╕рдмрд╕реЗ рдмрдбрд╝рд╛ рдорд╛рди 1 рд╣реИред
HCF(p1тАЛ,p2тАЛ)=1
C рд╕рд╣реА рд╣реИ рдХреНрдпреЛрдВрдХрд┐ рдПрдХрдорд╛рддреНрд░ рдзрдирд╛рддреНрдордХ рдкреВрд░реНрдгрд╛рдВрдХ рдЬреЛ рдХрд┐рдиреНрд╣реАрдВ рджреЛ рднрд┐рдиреНрди рдЕрднрд╛рдЬреНрдп рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЛ рд╡рд┐рднрд╛рдЬрд┐рдд рдХрд░рддрд╛ рд╣реИ рд╡рд╣ 1 рд╣реИ, рдЗрд╕рд▓рд┐рдП рдЙрдирдХрд╛ HCF 1 рд╣реЛрддрд╛ рд╣реИред
рдпрд╣ рдЕрд╡рдзрд╛рд░рдгрд╛ 'рд╕рд╛рдкреЗрдХреНрд╖ рдЕрднрд╛рдЬреНрдп' (рдпрд╛ рд╕рд╣-рдЕрднрд╛рдЬреНрдп) рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреА рдкрд░рд┐рднрд╛рд╖рд╛ рдХреЛ рд╕рдордЭрдиреЗ рдХреЗ рд▓рд┐рдП рдЖрдзрд╛рд░рднреВрдд рд╣реИ, рдЬрд╣рд╛рдБ HCF(a,b)=1 рд╣реЛрддрд╛ рд╣реИред