洛谷——P2626 斐波那契数列（升级版）矩阵

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int mod=1<<31;
int n,answer,s;
struct Node
{
    int m[3][3];
    Node(){memset(m,0,sizeof(m));}
}mb,ans;
Node operator*(Node a,Node b)
{
    Node c;
    for(int i=1;i<=2;i++)
     for(int j=1;j<=2;j++)
      for(int k=1;k<=2;k++)
       c.m[i][j]=(c.m[i][j]%mod+a.m[i][k]*b.m[k][j]%mod)%mod;
    return c;
}
int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();
    return x*f;
}
int main()
{
    n=read();
    ans.m[1][1]=ans.m[2][2]=1;
    mb.m[1][1]=mb.m[1][2]=mb.m[2][1]=1;
    while(n)
    {
        if(n&1) ans=ans*mb;
        mb=mb*mb;n>>=1;
    }
    answer=ans.m[1][2];
    printf("%d=",answer);
    for(int i=2;i<=answer;i++)
    {
        while(answer%i==0)
        {
            s++;answer/=i;
            if(s>1) printf("*");
            printf("%d",i);
         } 
    }
    return 0;
}