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也一起输出)
思路:
程序:
#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]);
}
}