热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

LightOJ1070AlgebraicProblem矩阵快速幂

题意:给你pa+b,qab算出(a^n+b^)mod2^64做法:mod2^64所以开unsignedlonglong,llu就行了,达到上限会自动取模的。然后就是公式了

题链:http://lightoj.com/volume_showproblem.php?problem=1070

1070 - Algebraic Problem
技术分享 PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 32 MB

Given the value of a+b and ab you will have to find the value of an+bna and b not necessarily have to be real numbers.

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains three non-negative integers, p, q and n. Here p denotes the value of a+b and q denotes the value of ab. Each number in the input file fits in a signed 32-bit integer. There will be no such input so that you have to find the value of 00.

Output

For each test case, print the case number and (an+bn) modulo 264.

Sample Input

Output for Sample Input

2

10 16 2

7 12 3

Case 1: 68

Case 2: 91

题意:

给你p=a+b, q=ab

算出 (a^n+b^)mod2^64

做法:

mod 2^64所以开 unsigned long long ,llu 就行了,达到上限会自动取模的。

然后就是公式了。我是在推公式中找到的规律。

a^2+b^2=(a+b)*(a+b)-2*a*b

a^3+b^3=(a^2+b^2)*(a+b)-a*b(a+b)

a^4+b^4=(a^3+b^3)*(a+b)-a*b(a^2+b^2)

设G(n)=a^n+b^n

G(n)=G(n-1)*p-G(G-2)*q

然后就是快速幂了。.

#include
#include
#define Matr 5 //矩阵大小,注意能小就小   矩阵从1开始   所以Matr 要+1   最大可以100
#define ll unsigned long long
struct mat//矩阵结构体,a表示内容,size大小 矩阵从1开始   但size不用加一
{
    ll a[Matr][Matr];
    mat()//构造函数
    {
        memset(a,0,sizeof(a));
    }
};
int Size=  2; 

mat multi(mat m1,mat m2)//两个相等矩阵的乘法,对于稀疏矩阵,有0处不用运算的优化 
{
    mat ans=mat(); 
    for(int i=1;i<=Size;i++)
        for(int j=1;j<=Size;j++)
            if(m1.a[i][j])//稀疏矩阵优化 
                for(int k=1;k<=Size;k++)
                    ans.a[i][k]=(ans.a[i][k]+m1.a[i][j]*m2.a[j][k]); //i行k列第j项
    return ans;
}

mat quickmulti(mat m,ll n)//二分快速幂 
{
    mat ans=mat();
    int i;
    for(i=1;i<=Size;i++)ans.a[i][i]=1;
    while(n)
    {
        if(n&1)ans=multi(m,ans);//奇乘偶子乘 挺好记的.
        m=multi(m,m);
        n>>=1;
    }
    return ans;
}

void print(mat m)//输出矩阵信息,debug用   
{  
    int i,j;  
    printf("%d\n",Size);  
    for(i=1;i<=Size;i++)  
    {  
        for(j=1;j<=Size;j++)
			printf("%llu ",m.a[i][j]);  
        printf("\n");  
    }  
}  
int main()
{  
	/*
	ll a,b;
	while(scanf("%llu",&a)!=EOF)
		printf("%llu\n",-a+18446744073709551615+1);
	*/
	int t;
	int cas=1;
	scanf("%d",&t);
	while(t--)
	{
		ll p,q,n;
		int p1,q1;
		scanf("%lld%lld%llu",&p,&q,&n);// p a+b q ab 



		ll tem=18446744073709551615-q+1;

		mat gouzao=mat(),chu=mat();//构造矩阵  初始矩阵   
		chu.a[1][1]=p;
		chu.a[1][2]=p*p+2*tem;
		chu.a[1][3]=q;
		printf("Case %d: ",cas++);
		if(n==0)
			printf("2\n");
		else if(n==1)
			printf("%llu\n",p);
		else if(n==2)
			printf("%llu\n",p*p+2*tem);
		else
		{ 
			gouzao.a[1][1]=0;
			gouzao.a[2][1]=1;
			gouzao.a[1][2]=tem;
			gouzao.a[2][2]=p;  
			//print(gouzao);
			printf("%llu\n",multi(chu,quickmulti(gouzao,n-2)).a[1][2]); 
		} 
	} 
	return 0;
}

/*
ans^=n -
mat ans=mat();
ans.size=Size;
初始化ans矩阵
ans=quickmulti(ans,n,mod);

void print(mat m)//输出矩阵信息,debug用 
{
    int i,j;
    printf(%dn,m.size);
    for(i=1;i=m.size;i++)
    {
        for(j=1;j=m.size;j++)printf(%d ,m.a[i][j]);
        printf(n);
    }
}
*/









版权声明:本文为博主原创文章,未经博主允许不得转载。

LightOJ 1070 - Algebraic Problem 矩阵快速幂


推荐阅读
  • 本文探讨了如何通过最小生成树(MST)来计算严格次小生成树。在处理过程中,需特别注意所有边权重相等的情况,以避免错误。我们首先构建最小生成树,然后枚举每条非树边,检查其是否能形成更优的次小生成树。 ... [详细]
  • QUIC协议:快速UDP互联网连接
    QUIC(Quick UDP Internet Connections)是谷歌开发的一种旨在提高网络性能和安全性的传输层协议。它基于UDP,并结合了TLS级别的安全性,提供了更高效、更可靠的互联网通信方式。 ... [详细]
  • 深入理解 Oracle 存储函数:计算员工年收入
    本文介绍如何使用 Oracle 存储函数查询特定员工的年收入。我们将详细解释存储函数的创建过程,并提供完整的代码示例。 ... [详细]
  • 深入理解Cookie与Session会话管理
    本文详细介绍了如何通过HTTP响应和请求处理浏览器的Cookie信息,以及如何创建、设置和管理Cookie。同时探讨了会话跟踪技术中的Session机制,解释其原理及应用场景。 ... [详细]
  • 本文介绍了一款用于自动化部署 Linux 服务的 Bash 脚本。该脚本不仅涵盖了基本的文件复制和目录创建,还处理了系统服务的配置和启动,确保在多种 Linux 发行版上都能顺利运行。 ... [详细]
  • 本文介绍如何通过Windows批处理脚本定期检查并重启Java应用程序,确保其持续稳定运行。脚本每30分钟检查一次,并在需要时重启Java程序。同时,它会将任务结果发送到Redis。 ... [详细]
  • Vue 2 中解决页面刷新和按钮跳转导致导航栏样式失效的问题
    本文介绍了如何通过配置路由的 meta 字段,确保 Vue 2 项目中的导航栏在页面刷新或内部按钮跳转时,始终保持正确的 active 样式。具体实现方法包括设置路由的 meta 属性,并在 HTML 模板中动态绑定类名。 ... [详细]
  • 2023 ARM嵌入式系统全国技术巡讲旨在分享ARM公司在半导体知识产权(IP)领域的最新进展。作为全球领先的IP提供商,ARM在嵌入式处理器市场占据主导地位,其产品广泛应用于90%以上的嵌入式设备中。此次巡讲将邀请来自ARM、飞思卡尔以及华清远见教育集团的行业专家,共同探讨当前嵌入式系统的前沿技术和应用。 ... [详细]
  • 如何在WPS Office for Mac中调整Word文档的文字排列方向
    本文将详细介绍如何使用最新版WPS Office for Mac调整Word文档中的文字排列方向。通过这些步骤,用户可以轻松更改文本的水平或垂直排列方式,以满足不同的排版需求。 ... [详细]
  • 理解存储器的层次结构有助于程序员优化程序性能,通过合理安排数据在不同层级的存储位置,提升CPU的数据访问速度。本文详细探讨了静态随机访问存储器(SRAM)和动态随机访问存储器(DRAM)的工作原理及其应用场景,并介绍了存储器模块中的数据存取过程及局部性原理。 ... [详细]
  • 几何画板展示电场线与等势面的交互关系
    几何画板是一款功能强大的物理教学软件,具备丰富的绘图和度量工具。它不仅能够模拟物理实验过程,还能通过定量分析揭示物理现象背后的规律,尤其适用于难以在实际实验中展示的内容。本文将介绍如何使用几何画板演示电场线与等势面之间的关系。 ... [详细]
  • MySQL中枚举类型的所有可能值获取方法
    本文介绍了一种在MySQL数据库中查询枚举(ENUM)类型字段所有可能取值的方法,帮助开发者更好地理解和利用这一数据类型。 ... [详细]
  • 本文介绍如何在应用程序中使用文本输入框创建密码输入框,并通过设置掩码来隐藏用户输入的内容。我们将详细解释代码实现,并提供专业的补充说明。 ... [详细]
  • 本文介绍如何通过SQL查询从JDE(JD Edwards)系统中提取所有字典数据,涵盖关键表的关联和字段选择。具体包括F0004和F0005系列表的数据提取方法。 ... [详细]
  • 本文详细介绍了如何通过命令行启动MySQL服务,包括打开命令提示符窗口、进入MySQL的bin目录、输入正确的连接命令以及注意事项。文中还提供了更多相关命令的资源链接。 ... [详细]
author-avatar
as1dzx
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有