hdu 3221 Brute-force Algorithm(高速幂取模,矩阵高速幂求fib)

hdu 3221 Brute-force Algorithm(高速幂取模,矩阵高速幂求fib)

大家好,又见面了,我是全栈君。

http://acm.hdu.edu.cn/showproblem.php?pid=3221

一晚上搞出来这么一道题。。Mark。


给出这么一个程序。问funny函数调用了多少次。

我们定义数组为所求:f[1] = a,f[2] = b, f[3] = f[2]*f[3]……f[n] = f[n-1]*f[n-2]。相应的值表示也可为a^1*b^0%p。a^0*b^1%p,a^1*b^1%p,…..a^fib[n-3]*b^fib[n-2]%p。即a,b的指数从n=3以后与fib数列一样。


由于n非常大。fib[n]也想当大。

a^fib[n]%p能够利用a^fib[n]%p = a^(fib[n]%phi[p]+phi[p])%p进行降幂,条件时fib[n]>=phi[p]。求fib[n]%phi[p]能够构造矩阵。利用矩阵高速幂求fib[n]%phi[p]。


#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL long long
#define _LL __int64
#define eps 1e-12
#define PI acos(-1.0)
#define C 240
#define S 20
using namespace std;
const int maxn = 110;

struct matrix
{
    LL mat[3][3];
    void init()
    {
        memset(mat,0,sizeof(mat));
        for(int i = 0; i < 2; i++)
            mat[i][i] = 1;
    }
} m;

LL a,b,p,n,phi_p;
LL fib[10000000];

//phi[p]
LL Eular(LL num)
{
    LL res = num;
    for(int i = 2; i*i <= num; i++)
    {
        if(num%i == 0)
        {
            res -= res/i;
            while(num%i == 0)
                num /= i;
        }
    }
    if(num > 1)
        res -= res/num;
    return res;
}
//矩阵相乘
matrix mul_matrix(matrix x, matrix y)
{
    matrix ans;
    memset(ans.mat,0,sizeof(ans.mat));
    for(int i = 0; i < 2; i++)
    {
        for(int k = 0; k < 2; k++)
        {
            if(x.mat[i][k] == 0) continue;
            for(int j = 0; j < 2; j++)
            {
                ans.mat[i][j] = (ans.mat[i][j] + x.mat[i][k]*y.mat[k][j])%phi_p;
            }
        }
    }
    return ans;
}
//a^t%phi_p
LL pow_matrix(LL t)
{
    matrix a,b;
    a.mat[0][0] = a.mat[0][1] = a.mat[1][0] = 1;
    a.mat[1][1] = 0;
    b.init();
    while(t)
    {
        if(t&1)
            b = mul_matrix(a,b);
        a = mul_matrix(a,a);
        t >>= 1;
    }
    return b.mat[0][0];
}
//a^t%p
LL pow(LL a, LL t)
{
    LL res = 1;
    a %= p;
    while(t)
    {
        if(t&1)
            res = res*a%p;
        a = a*a%p;
        t >>= 1;
    }
    return res;
}
//a^fib[t]%p转化为a^(fib[t]%phi[p]+phi[p])%p,fib[t] >= phi[p]。
LL solve(LL a, LL t)
{
    fib[0] = 1;
    fib[1] = 1;
    int i;
    for(i = 2; i <= t; i++)
    {
        fib[i] = fib[i-1] + fib[i-2];
        if(fib[i] >= phi_p)
            break;
    }
    if(i <= t) //当满足条件fib[t] >= phi[p]时,进行降幂
    {
        LL c = pow_matrix(t) + phi_p;
        return pow(a,c);
    }
    else
        return pow(a,fib[t]);
}

int main()
{
    int test;
    scanf("%d",&test);
    for(int item = 1; item <= test; item++)
    {
        scanf("%lld %lld %lld %lld",&a,&b,&p,&n);
        printf("Case #%d: ",item);
        if(n == 1)
        {
            printf("%lld\n",a%p);
            continue;
        }
        if(n == 2)
        {
            printf("%lld\n",b%p);
            continue;
        }
        if(n == 3)
        {
            printf("%lld\n",a*b%p);
            continue;
        }
        if(p == 1)
        {
            printf("0\n");
            continue;
        }
        phi_p = Eular(p);
        LL res = solve(a,n-3)*solve(b,n-2)%p;
        printf("%lld\n",res);
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116402.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Word编辑中的域代码详解

    Word编辑中的域代码详解编辑域的对话框关于域的快捷键:Ctrl+F9组合键——快速插入域定义符“{}”(注意:这个花括号不能用键盘输入)Shift+F9组合键——显示或者隐藏指定的域代码Alt+F9组合键——显示或者隐藏文档中所有域代码F9键——更新单个域上表中,选中每一个实例用鼠标右键单击,选“切换域代码”(或者直接按Shift+F9组合键),就可以看到域代码,再按Shift+F9组合键回到…

  • c语言读取bmp图像_opencv 图像处理

    c语言读取bmp图像_opencv 图像处理以前都是使C语言中File*、fopen、fread等操作文件,这几天学习了C++IO标准库,就应用来读取bmp图像。

  • autoconf产生Makefile流程

    autoconf产生Makefile流程生成Makefile的流程。参考http://www.ibm.com/developerworks/cn/linux/l-makefile/首先进入project目录,在该目录下运行一系列命令,创建和修改几个文件,就可以生成符合该平台的Makefile文件,操作过程如下:1)运行autoscan命令2)将configure.scan文件重命名为configure.

  • MODIS数据介绍——波段、产品

    MODIS数据介绍——波段、产品MODIS是搭载在terra和aqua卫星上的传感器,MODIS扫描周期为1.477秒,每条扫描线沿扫描方向有1354个Pixels,沿卫星轨道方向有10个1KMD的IFOV。在每个IFOV中,1KM分辨率波段有1个采样,500M分辨率波段有4个采样,250M波段有16个采样。通过网址进行下载:https://ladsweb.modaps.eosdis.nasa.gov/对于MODIS的波段…

  • QueueUserWorkItem 初步学习

    QueueUserWorkItem 初步学习 DWORDWINAPITestThreadPool(PVOIDpContext);CRITICAL_SECTIONg_cs;int_tmain(intargc,_TCHAR*argv[]){ InitializeCriticalSection(&g_cs); SECURITY_ATTRIBUTESsa; sa.bInheritHandle=TRUE; sa.nLen

  • 模型剪枝学习笔记 — EagleEye: Fast Sub-net Evaluation for Efficient Neural Network Pruning

    模型剪枝学习笔记 — EagleEye: Fast Sub-net Evaluation for Efficient Neural Network Pruning论文:https://arxiv.org/abs/2007.02491代码:https://github.com/anonymous47823493/EagleEye这篇论文一定要好好研究下,提出该剪枝方法的是暗物智能科技&中山大学,当初去面试过该公司,聊了将近一小时,大部分是关于剪枝的内容。。。。。。。可惜自己真实菜如狗。。。。。…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号