HDU 2281 Square Number Pell方程
2024-08-31 17:07:59
http://acm.hdu.edu.cn/showproblem.php?pid=2281
又是一道Pell方程
化简构造以后的Pell方程为
求出其前15个解,但这些解不一定满足等式,判断后只有5个满足的情况,直接判断即可
求法可以参照上一篇日志: http://www.cnblogs.com/Felix-F/p/3223323.html
struct matrix
{
LL ma[][];
};
int n = ;
LL nn[],xx[];
matrix operator * (matrix a,matrix b)
{
matrix temp;
memset(temp.ma,,sizeof(temp.ma));
for(int i = ; i < n ; i++)
for(int j = ; j < n ; j++)
for(int k = ; k < n ; k++)
temp.ma[i][j] = temp.ma[i][j] + (a.ma[k][i] * b.ma[j][n-k-]);
return temp;
}
matrix operator + (matrix a,matrix b)
{
for(int i = ; i < n ; i++)
for(int j = ; j < n ; j++)
a.ma[i][j] = (a.ma[i][j] + b.ma[i][j]) ;
return a;
}
void init()
{
matrix a;
a.ma[][] = ;
a.ma[][] = ;
a.ma[][] = ;
a.ma[][] = ;
matrix temp = a;
nn[] = ;
xx[] = ;
int cnt = ;
for(int i = ;i <= ; i++)
{
if(i% == )
{
LL s1 = temp.ma[][] * + temp.ma[][] * ;
nn[cnt] = (s1 - ) / ;
LL s2 = temp.ma[][] * + temp.ma[][] * ;
xx[cnt++] = s2;
}
temp = temp*a;
}
}
int main()
{
init();
LL N;
while(cin>>N && N)
{
for(int i = ; i >= ; i--)
{
if(N >= nn[i])
{
cout<<nn[i]<<" "<<xx[i]<<endl;
break;
}
}
}
return ;
}
最新文章
- >;hibernate-session中的方法
- UINavigationItem UINavigationBar 关系分析[转]
- iOS网络-01-NSURLRequest与NSURLConnection
- SharePoint 2013 Nintex Workflow 工作流帮助(十三)
- poj1651 区间dp
- Java 理论与实践: 处理 InterruptedException(转)
- JAVA printWriter中write()和println()区别
- CloseHandle 函数--关闭一个句柄
- “无文件”恶意软件的威力:悄无声息一夜之间从ATM机中窃取80万美元
- php面试之数据结构和算法
- Objective-C 中的 BOOL
- NOIP 2019游记
- 数据库和SQL面试题基础知识(持续更新)
- MySQL 中触发器的应用
- stock
- IOS 应用官方接口地址
- 05-Vim命令合集
- windows 下获取当前进程的线程数量
- MFC将二进制文件导入资源后释放
- 使用嵌入文档Here Documents