HDU 3292
2024-08-31 09:56:03
快速幂模+佩尔方程
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
const int Mod=8191;
struct Matrax {
int m[3][3];
};
Matrax a,per; void slove(int d,int &x1,int &y1){
y1=1;
while(true){
x1=(int)sqrt(1.0*d*y1*y1+1);
if(x1*x1-d*y1*y1==1)
break;
y1++;
}
} Matrax multi(Matrax a,Matrax b){
Matrax c;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
c.m[i][j]=0;
for(int k=0;k<2;k++)
c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%Mod;
}
}
return c;
} Matrax Power(int k){
Matrax ans=per,p=a;
while(k){
if(k&1){
ans=multi(ans,p);
}
k>>=1;
p=multi(p,p);
}
return ans;
} int main(){
int n,k,x1,y1,xt,yt,xn,yn;
while(scanf("%d%d",&n,&k)!=EOF){
int sq=(int)sqrt(n*1.0);
if(sq*sq==n){
printf("No answers can meet such conditions\n");
continue;
}
slove(n,x1,y1);
per.m[0][0]=per.m[1][1]=1;
per.m[0][1]=per.m[1][0]=0;
a.m[0][0]=x1; a.m[0][1]=n*y1;
a.m[1][0]=y1; a.m[1][1]=x1;
Matrax ans=Power(k-1);
int ansx=0;
ansx=(ans.m[0][0]*x1+ans.m[0][1]*y1)%Mod;
printf("%d\n",ansx);
}
return 0;
}
最新文章
- 基于stm32f4的ucGUI通过外部flash存储汉字库显示任意英文字符和汉字组合(控件可用)
- Android—9.png的制作和去除黑线
- UvaOJ10369 - Arctic Network
- 设置php下载文件的超时时间
- 页面静态化1 --- 概念(Apache内置压力测试工具使用方法)
- 【转】Problems with HTTPS, HttpWebRequest, and iOS?
- jsp基础知识(基本的语法及原理)
- Java实现多线程邮件发送
- java语言写文件内容
- Spring(3.2.3) - Beans(8): 基于 Annotation 的配置
- 使用Navicat for Oracle 出现的错误
- 160G 视频教程(Java+Android+项目视频)免费下载
- 用php+ajax新建流程(请假、进货、出货等)
- 找不到包含 OwinStartupAttribute 的程序集。 - 找不到包含 Startup 或 [AssemblyName].Startup 类的程序集。
- Jquery Ajax type的4种类型
- Lucene 学习资料
- logstash的output配置中指定elasticsearch的template
- python3+Robot Framework+PyCharm第一个WEB UI自动化用例
- gitbook 入门教程之发布电子书
- php 两次encodeURI,解决浏览器跳转请求页乱码报错找不到页面的bug