欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

So Easy! hdu4565

程序员文章站 2022-06-04 12:09:54
...

So Easy!(点击即可跳转)

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


 

Problem Description
  A sequence Sn is defined as:

So Easy! hdu4565


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!

So Easy! hdu4565

 

 

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

 

Output
  For each the case, output an integer Sn.
 

 

Sample Input
2 3 1 2013
2 3 2 2013
2 2 1 2013 
 

 

Sample Output
4
14
4
 
 
大致题意:已知a,b, 求So Easy! hdu4565

So Easy! hdu4565

以下是ac代码:

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;

typedef long long ll;

struct matrix{
    ll x[20][20];
    ll n, m;
    matrix(){memset(x, 0, sizeof(x));}
};

ll m;
matrix multiply(matrix &mata, matrix &matb)
{
    matrix c;
    c.n = mata.n;
    c.m = matb.m;
    for(int i = 1; i <= mata.n; i++){
        for(int j = 1; j <= mata.m; j++){
            c.x[i][j] = 0;
            for(int k = 1; k <= matb.m; k++){
                c.x[i][j] += mata.x[i][k] * matb.x[k][j];
                c.x[i][j] %= m;
            }
        }
    }
    return c;
}

ll a, matb;

matrix mpow(matrix &origin, ll n)
{
    matrix res;
    res = origin;
    matrix change;
    change.n = change.m = 2;
    change.x[1][1] = 2 * a;
    change.x[1][2] = 1;
    change.x[2][1] = matb - a * a;
    change.x[2][2] = 0;

    while(n > 0){
        if(n & 1)res = multiply(res, change);
        change = multiply(change, change);
        n >>= 1;
    }
    return res;
}

int main()
{
    ll n;
    while(cin>>a>>matb>>n>>m){
        if(n == 1){
            printf("%lld\n", 2 * a);
            continue;
        }else if(n == 2){
            ll ans = (ll)(ceil((a +sqrt(matb)) * (a +sqrt(matb)))) % m;
            printf("%lld\n", ans);
            continue;
        }

        matrix mat;
        mat.n = 1;
        mat.m = 2;
        ll ans = (ll)(ceil((a +sqrt(matb)) * (a +sqrt(matb)))) % m;
        mat.x[1][1] = ans;

        mat.x[1][2] = 2 * a;
        mat = mpow(mat, n - 1);
        printf("%lld\n", (mat.x[1][2] + m) % m);
    }
    return 0;
}

 

相关标签: 矩阵快速幂 HDU