欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

5845. 【NOIP2018提高组模拟】西西算数

程序员文章站 2022-03-31 08:08:02
...

题目大意:

西西是可爱的孩子,他总是喜欢算数,每天都在算啊算啊……这天,西西学会了如何进行指数运算,
于是他算出了√5=2.2360679774997896964091736687313
然后他又算出了 (3 + √5)^2 = 27.4164079… (3 + √5)^5 = 3935.73982…. 西西顿时对(3 + √5)^n产生了浓厚的兴趣。但对于N=2000000000时,西西一下子晕了,算了好久也没算出来,他只好求助于你。为了你的计算方便,你只需要告诉西西(3 + √5)^n 的整数部分的最后三位就行了(不够的在前面补0,如果有前导0也一起输出)

思路:

5845. 【NOIP2018提高组模拟】西西算数

程序:

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>

int n,t,c[2],g[2],cnt;
struct data{int a[2][2];}f,f1,f2;

void cheng(data a,data b){
    for (int i=0;i<=1;i++)
     for (int j=0;j<=1;j++){
        f2.a[i][j]=0;
        for (int k=0;k<=1;k++)
            f2.a[i][j]=(f2.a[i][j]+a.a[i][k]*b.a[k][j])%1000;
     }
    for (int i=0;i<=1;i++)
     for (int j=0;j<=1;j++)
        f.a[i][j]=f2.a[i][j];
}

void mul(int x){
    if (x==1) return;
    mul(x/2);
    cheng(f,f);
    if (x%2==1) cheng(f,f1);
}

int main(){
    freopen("Count.in","r",stdin);
    freopen("Count.out","w",stdout);
    scanf("%d",&t);
    while (t){
        t--;
        f.a[0][0]=6; f.a[1][0]=-4;
        f.a[0][1]=1; f.a[1][1]=0;
        f1.a[0][0]=6; f1.a[1][0]=-4;
        f1.a[0][1]=1; f1.a[1][1]=0;
        scanf("%d",&n);
        g[0]=28;
        g[1]=6;
        if (n==1) printf("006\n");
        if (n==2) printf("028\n");
        if (n<=2) continue;
        mul(n-2);
        memset(c,0,sizeof(c));
        for (int i=0;i<2;i++)
         for (int j=0;j<2;j++)
          c[j]=(c[j]+g[i]*f.a[i][j])%1000;
        cnt++;
        printf("Case #%d: ",cnt);
        c[0]=(c[0]-1+1000)%1000;
        if (c[0]<100) printf("0");
        if (c[0]<10) printf("0");
        printf("%d\n",c[0]);
    }
}
相关标签: 何嘉阳