通用版1.I - 辗转相除法求最大公约数

xiaoxiao2021-02-28  33

#include <stdio.h> #include <stdlib.h> int main() { int n,a,t,u,v,r,s,w; scanf("%d",&w); while(w--){ scanf("%d",&n); int count=1; //scanf("%d",&); while(n--){ scanf("%d",&a); if(count++==1){ s=a; continue; } u=s; v=a; if(s<a){ t=s; s=a; a=t; } while(1){ r=s%a; if(r==0)break; s=a; a=r; } s=u/a*v; } printf("%d\n",s); } return 0; }

辗转相除法求最大公约数就是较大数除以较小数,然后得到余数,再用除数除以这个余数,反复这么做,直到余数为零,最后的除数就是最大公约数

转载请注明原文地址: https://www.6miu.com/read-2624625.html

最新回复(0)