poj2706-麦森数-高精度快速幂

struct_liao

于 2016-08-13 00:05:08 发布

阅读量1.1k

点赞数

分类专栏：模板

本文链接：https://blog.csdn.net/struct_liao/article/details/52196537

版权

模板专栏收录该内容

10 篇文章

订阅专栏

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int a[610],b[610],c[610],d,n,i,j,ldy;
int main(){
    scanf("%d",&n);
    int ldy=ceil( n* log10(2) );
    printf("%d\n",ldy);
    a[1]=2;
    b[1]=1;
    while(n!=0){
        for(i=1;i<=510;i++)
            c[i]=0;
        
        if(n%2==1){
            for(i=1;i<=500;i++)
                for(j=1;j<=500;j++)
                    if(i+j<=510){
                    c[i+j-1]=c[i+j-1]+b[i]*a[j];
                    c[i+j]=c[i+j]+c[i+j-1]/10;
                    c[i+j-1]=c[i+j-1]%10;
                }
            for(i=1;i<=510;i++)
                b[i]=c[i];

            n--;
            continue;
        }

        for(i=1;i<=500;i++)
            for(j=1;j<=500;j++)
                if(i+j<=510){
                c[i+j-1]=c[i+j-1]+a[i]*a[j];
                c[i+j]=c[i+j]+c[i+j-1]/10;
                c[i+j-1]=c[i+j-1]%10;
            }
        for(i=1;i<=510;i++)
            a[i]=c[i];
        n=n/2;
    }

    d=500;
    b[1]--;
    for(i=1;i<=10;i++){
        for(j=1;j<=50;j++){
            printf("%d",b[d]);
            d--;
        }
    printf("\n");
    }
   
    return 0;
}