hdu 1722 数论题

公式q+p-gcd(p,q)
gcd 求两个数的最大公约数 也就是两种分法重复的部分
先把蛋糕分成q份，然后把蛋糕拼在一起，然后再分成p份。
分成q份需要切q-1刀，分成p份需要切p-1刀，但是会有重复，减去重复的部分就是gcd(p,q)

• 证明的详细过程参考网站http://www.shuxueweb.com/shuxuebolan/qiuti/shuxuebolan_9112.html

• #include<stdio.h>
  int main()
  {
      int n,m,t,p;
      while(scanf("%d %d",&n,&m)!=EOF)
      {
          p=n+m;
          while(n!=0)//求最大公约数
          {
              t=m%n;
              m=n;
              n=t;
          }
          printf("%d\n",p-m);
      }
      return 0;
  }