- #include<iostream>
- using namespace std;
- long long map[2][2]={1LL,0LL,1LL,0LL};
- long long E[2][2]={1LL,1LL,1LL,0LL};
- long long fun(long long x);
- void _copy(long long (*by_map)[2],long long (*to_map)[2]);
- void _cal(long long (*map1)[2],long long (*map2)[2],long long (*new_map)[2]);
- int main()
- {
- long long n;
- while(cin>>n){
- cout<<fun(n)<<endl;
- }
- }
- long long fun(long long x)
- {
- if(x==1)
- {
- _copy(map,E);
- }else{
- long long temp[2][2];
- _copy(temp,map);
- fun(x/2);
- _copy(temp,map);
- _cal(temp,temp,map);
- if(x%2==1)
- {
- _copy(temp,map);
- _cal(temp,E,map);
- }
- }
- return map[0][1];
- }
- void _copy(long long (*by_map)[2],long long (*to_map)[2])//将to_map 赋值到 by_map
- {
- by_map[0][0]=to_map[0][0];
- by_map[0][1]=to_map[0][1];
- by_map[1][0]=to_map[1][0];
- by_map[1][1]=to_map[1][1];
- }
- void _cal(long long (*map1)[2],long long (*map2)[2],long long (*new_map)[2])//MAP1*MAP2=NEW_MAP
- {
- long long mod_val=10000;
- new_map[0][0]=((map1[0][0]*map2[0][0])%mod_val+(map1[0][1]*map2[1][0])%mod_val)%mod_val;
- new_map[0][1]=((map1[0][0]*map2[0][1])%mod_val+(map1[0][1]*map2[1][1])%mod_val)%mod_val;
- new_map[1][0]=((map1[1][0]*map2[0][0])%mod_val+(map1[1][1]*map2[1][0])%mod_val)%mod_val;
- new_map[1][1]=((map1[1][0]*map2[0][1])%mod_val+(map1[1][1]*map2[1][1])%mod_val)%mod_val;
- }
- //该片段来自于http://www.codesnippet.cn/detail/1405201512577.html
来源: http://www.codesnippet.cn/detail/1405201512577.html