{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://www.xiaopingtou.cn//data/attach/topic/topicKPo7gB.jpg', '推荐 u013776390 的文章《UVA 10655 Contemplation! Algebra(构造矩阵)》','https://www.xiaopingtou.net/article-58961.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}
此文章可以使用目录功能哟↑(点击上方[+])
Accept: 0 Submit: 0
Time Limit: 3000 MS
Given the value of a+b and ab you will have to find the value of 
The input file contains several lines of inputs. Each line except the last line contains 3 non-negative integers p, q and n. Here p denotes the value of a+b and q denotes the value of ab. Input is terminated by a line containing only two zeroes. This line should
not be processed. 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
.
For each line of input except the last one produce one line of output. This line contains the value of . You can always assume that
fits in a signed 64-bit integer.
10 16 2
7 12 3
0 0
68
91
解题思路:
【题意】
给你a+b,ab,n的值,求
【类型】
矩阵构造
【分析】
首先,给你a+b,ab,可能第一想法是a,b为方程
的两个根(韦达定理根深蒂固)
但是此题若是把a,b求解出来显然是不可取的
①方程不一定有实根
②就算是实根,精度不高
那么,换个思路,对进行化简,令f(n)=,则
就这样,递推式出来了,那么就可以转换成矩阵来求解
p=a+b;q=ab 特判n=0,n=1,n=2的情况,貌似n=2可以不用特判 n=0时,
n=1时,a+b=p
n=2时,(a+b)*(a+b)-2ab=p*p-2*q
另外,题目要求当且仅当输入的一行仅有0 0时,输入结束
故只判断p!=0&&q!=0是不对的,因为数据0 0 n(n≠0)是合法的
【时间复杂度&&优化】
O(logn)
题目链接→UVA 10655 Contemplation! Algebra
UVA Problem 10655 Contemplation! Algebra
Accept: 0 Submit: 0Time Limit: 3000 MS
Problem Description
Given the value of a+b and ab you will have to find the value of Input
The input file contains several lines of inputs. Each line except the last line contains 3 non-negative integers p, q and n. Here p denotes the value of a+b and q denotes the value of ab. Input is terminated by a line containing only two zeroes. This line should
not be processed. 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
. Output
For each line of input except the last one produce one line of output. This line contains the value of . You can always assume that
fits in a signed 64-bit integer. Sample Input
10 16 27 12 3
0 0
Sample Output
6891
Problem Idea
解题思路:
【题意】给你a+b,ab,n的值,求
【类型】
矩阵构造
【分析】
首先,给你a+b,ab,可能第一想法是a,b为方程
的两个根(韦达定理根深蒂固)
但是此题若是把a,b求解出来显然是不可取的
①方程不一定有实根
②就算是实根,精度不高
那么,换个思路,对进行化简,令f(n)=,则
就这样,递推式出来了,那么就可以转换成矩阵来求解
p=a+b;q=ab 特判n=0,n=1,n=2的情况,貌似n=2可以不用特判 n=0时,
n=1时,a+b=p
n=2时,(a+b)*(a+b)-2ab=p*p-2*q
另外,题目要求当且仅当输入的一行仅有0 0时,输入结束
故只判断p!=0&&q!=0是不对的,因为数据0 0 n(n≠0)是合法的
【时间复杂度&&优化】O(logn)
题目链接→UVA 10655 Contemplation! Algebra
Source Code
/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
#include
#include
#include
#include
#include
#include
#include