记录编号	437817	评测结果	AAAAAAAAAA
题目名称	[HNOI 2011] 数学作业	最终得分	100
用户昵称	天亮说晚安·	是否通过	通过
代码语言	C++	运行时间	0.016 s
提交时间	2017-08-14 18:48:06	内存使用	0.31 MiB

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;

ll n,m,ans[4][4],shu;
ll a[4][4],wei,tot,oola;

inline void cheng(ll aa[4][4],ll bb[4][4],ll to[4][4]){
     ll tmp[4][4]={0};
     for(int i=1;i<=3;i++)
       for(int j=1;j<=3;j++)
         for(int u=1;u<=3;u++)
           tmp[i][j]=(tmp[i][j]+aa[i][u]*bb[u][j]%m)%m;
     for(int i=1;i<=3;i++)
       for(int j=1;j<=3;j++)
          to[i][j]=tmp[i][j];
}

inline ll qpow(ll x,ll ci){
     x=x%m;  ll sum=1;
     while(ci){
	    if(ci&1) sum=sum*x%m;
	    ci=ci>>1;
	    x=x*x%m;
	 }
	 return sum;
}

inline ll oula(ll x){
	 ll num=x;
	 for(ll i=2;i*i<=num;i++)
	    if(x%i==0){
		    num=num-num/i;
		    while(x%i==0) x=x/i;
		}
     if(x>1) num=num-num/x;
	 return  num;
}

int main(){
freopen("mathwork.in","r",stdin);
freopen("mathwork.out","w",stdout);
     scanf("%lld%lld",&n,&m);
     ll p=n;    shu=1;    oola=oula(m);
	 while(p){wei++;p=p/10;}
     for(int i=1;i<=wei;i++){
     	 memset(a,0,sizeof(a));
     	 memset(ans,0,sizeof(ans));
     	 shu*=10;
		 a[2][1]=a[2][2]=a[3][1]=a[3][2]=a[3][3]=1;
	     a[1][1]=shu%m;  ans[1][1]=ans[2][2]=ans[3][3]=1;
	     ll q=shu-shu/10,oo=q;
		 if(i==wei) q=n-shu/10+1,oo=q;
		 while(q){
		    if(q&1) cheng(a,ans,ans);
		    q=q>>1;
		    cheng(a,a,a);
		 }
		 tot=(tot*qpow(10,(ll)(oo%oola*i+oola))%m+ans[2][1]*((shu/10-1)%m)%m+ans[3][1])%m;
	 }
	 if(tot<0)  tot+=m;
	 printf("%lld",tot);
}