HDU 5650 So easy！（not easy！）

天道Vax的时间宝藏

发布于 2021-08-11 10:44:23

2030

发布于 2021-08-11 10:44:23

So easy！

Time Limit: 2000/1000 MS (Java/Others)	Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 356	Accepted Submission(s): 39

A sequence Sn is defined as:

Where a, b, n, m are positive integers.┌x┐is the ceil of x. For example, ┌3.14┐=4. You are to calculate Sn. 　　You, a top coder, say: So easy!

Input

　　There are several test cases, each test case in one line contains four positive integers: a, b, n, m. Where 0< a, m < 2^15, (a-1)^2< b < a^2, 0 < b, n < 2^31.The input will finish with the end of file.

Output

　　For each the case, output an integer Sn.

SampleInput

2 3 1 2013
2 3 2 2013
2 2 1 2013

SampleOutput

4
14
4

题意理解：

正如你所见，题目就是求a+根号b的n次方的除m余数，so easy！，但是！，但是！，为什么提交后会wrong answer！好吧，可能数据太大，越界了，毕竟到了2^31这个数量级，那好吧，我用累乘的方法for循环一下，，然而！，然而！，Time Limit Exceeded。这说明什么？超时？可只有O(n)的的时间复杂度呀，，，不对，既然都n<2^31了，也就是说，要循环累乘上亿次，那真的是木的办法了，，还好接触过矩阵快速幂，也只能试试了，他把O(n)优化到了O(log(n))，几乎已经是最小的时间复杂度了。至于矩阵快速幂，这里不多做解析，模板拿过来套用即可。

参考网址：介绍快速幂算法：https://www.cnblogs.com/mjust/p/4419519.html

矩阵快速幂算法：https://blog.csdn.net/zhangxiaoduoduo/article/details/81807338

附上本题AC代码：

/**
 *
 * ━━━━━━神兽出没━━━━━━
/**
 *　　　　　　　　┏┓　　　┏┓+ +
 *　　　　　　　┏┛┻━━━┛┻┓ + +
 *　　　　　　　┃　　　　　　　┃ 　
 *　　　　　　　┃　　　━　　　┃ ++ + + +
 *　　　　　　 ████━█████+
 *　　　　　　　┃　　　　　　　┃ +
 *　　　　　　　┃　　　┻　　　┃
 *　　　　　　　┃　　　　　　　┃ + +
 *　　　　　　　┗━┓　　　┏━┛
 *　　　　　　　　　┃　　　┃　　　　　　　　　　　
 *　　　　　　　　　┃　　　┃ + + + +
 *　　　　　　　　　┃　　　┃　　　　Code is far away from bug with the animal protecting　　　　　
 *　　　　　　　　　┃　　　┃ + 　　　　神兽保佑,代码无bug　　
 *　　　　　　　　　┃　　　┃
 *　　　　　　　　　┃　　　┃　　+　　　　　　　　　
 *　　　　　　　　　┃　 　　┗━━━┓ + +
 *　　　　　　　　　┃ 　　　　　　　┣┓
 *　　　　　　　　　┃ 　　　　　　　┏┛
 *　　　　　　　　　┗┓┓┏━┳┓┏┛ + + + +
 *　　　　　　　　　　┃┫┫　┃┫┫
 *　　　　　　　　　　┗┻┛　┗┻┛+ + + +
 * ━━━━━━感觉萌萌哒━━━━━━
 *
 */
//1001题
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<deque>
#include<map>
#include<iomanip>
#include<queue>
#include<list>
#include<string>
#include<set>
#include<stack>
#include<vector>
typedef long long ll;
using namespace std;
ll a,b,n,m;
struct mat{
    ll ab[3][3];
    mat(){memset(ab, 0, sizeof(ab)); }
    mat operator *(const mat q){
        mat c;
        for(int i = 1; i <= 2; ++i)
            for(int j = 1; j <= 2; ++j)
            if(ab[i][j])
        for(int k = 1; k <= 2; ++k){
            c.ab[i][k] += ab[i][j] * q.ab[j][k];
            if (c.ab[i][k] >= m) c.ab[i][k]%= m;
        }return c;
    }
};

mat zhuanhuan(mat x, ll n){
    mat ans;
    ans.ab[1][1]=ans.ab[2][2]= 1;
    while(n){
        if (n&1) ans = ans*x;
        x = x * x;
        n >>= 1;
    }return ans;
}


int main(){
    while(cin>>a>>b>>n>>m){
        mat ans;
        a=a%m;
        b=b%m;
        
        
        ans.ab[1][1]=ans.ab[2][2]=a;
        ans.ab[1][2]=b;
        ans.ab[2][1]=1;
        
        
        ans = zhuanhuan(ans, n);
        
        ll sum = ans.ab[1][1];
        sum = (sum * 2) % m;
        printf("%lld\n",sum);
    }return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/08/16 ，如有侵权请联系 cloudcommunity@tencent.com 删除

https