kgcd ,fmod,fgcd

参考：NENU CS ACM模板made by tiankonguse 2.13 GCD

快速gcd:

位操作没学，真心不懂二进制，还是得学啊

code:

 int kgcd(){

   if(!a || !b)

      return a?a:b;

   if(!(a&) && !(b&))

      return kgcd(a>>,b>>)<<;

   if(!(b&))

      return kgcd(a,b>>);

   if(!(a&))

     return kgcd(a>>,b);

   return kgcd(b,a%b);

 }

在说fgcd之前先说一下fmod函数吧

fmod:

    原型：extern float fmod(float x, float y);

  头文件：#include <math.h>

    功能：计算x/y的余数

    说明：返回x-n*y，使用codeblocks编译符号同x。n=[x/y](向离开零的方向取整)

    举例：

  int main(){

         double x,y;

           x=24.238;

           y=;

        printf("%lf\n",fmod(x,y));

       }

   运行结果是 4.238

这个函数还可以取得某个数的小数点后的部分。如：

fload f = 1.234;

fmod(f,(int)f)即可得到小数点后的部分

fgcd:(实数的gcd)

模板：

#define eps 1e-8

double fgcd(double a,double b){

 if(b > -eps && b < eps){

        return a;

}

else{

return fgcd(b,fmod(a,b));

}

举例：

Apr 30,2014 codeforces

C. Ancient Berland Circus

题目大意：给出3个点，求最小面积的正多边形，使得这3个点为正多边形的顶点。

算法分析：

根据正多边形的性质，正多边形的每个顶点都在其外接圆上。

已知3个点，可以根据海伦公式求出三角形的面积S。然后根据正弦定理求出外接圆的半径R=abc/(4S)，根据余弦定理求出三个圆心角。

求出三个圆心角的最大公约数A，则正多边形由2*pi/A个小三角形组成。

根据正弦定理求出每个小三角形的面积S0，则答案即为S0*2*pi/A。

Code:

 #include <cstdio>

 #include <cmath>

 using namespace std;

 const double pi=acos(-),eps=1e-;

 double x[],y[],a,b,c,A,B,C,p,S,R,alpha,S0,n;

 double fgcd(double a,double b){

     if (fabs(b)<eps) return a;

     return fgcd(b,fmod(a,b));

 }

 int main(){

     for (int i=;i<;++i) scanf("%lf%lf",&x[i],&y[i]);

     a=sqrt((x[]-x[])*(x[]-x[])+(y[]-y[])*(y[]-y[]));

     b=sqrt((x[]-x[])*(x[]-x[])+(y[]-y[])*(y[]-y[]));

     c=sqrt((x[]-x[])*(x[]-x[])+(y[]-y[])*(y[]-y[]));

     A=*acos((b*b+c*c-a*a)//b/c);

     B=*acos((a*a+c*c-b*b)//a/c);

     C=*pi-A-B;

     p=(a+b+c)/;

     S=sqrt(p*(p-a)*(p-b)*(p-c));

     R=a*b*c//S;

     alpha=fgcd(fgcd(A,B),C);

     n=*pi/alpha;

     S0=R*R*sin(alpha)/;

     printf("%0.7lf\n",n*S0);

     return ;

 }

关于GCD的一些结论

1.有两个数p,q,gcd(p,q) = 1,则最大无法表示成px+qy(x >= 0 ,y >= 0)的数是pq-q-p.

2.区间内与n的gcd不小于m的数

输入m,n,求1-n之间中gcd(x,n) >= m 的x的个数。

找出N的所有大于等于M的因子（x1,x2,x3......xi）,然后设k = N/xi.

下面只需找出小于k且与k互质的数。

因为：设y小于k且与k互质，那么gcd(y*xi,k*xi) = xi,(xi为k的因子，且xi大于等于M)。

巴特西

kgcd ,fmod,fgcd

最新文章

热门文章