↓ Skip to main content
  1. Posts/

codeforces #368 div 2 C. Pythagorean Triples (构造,数学)

·953 words·2 mins
Note: This article is available in Chinese only. 本文暂无英文版本。 View original

题目链接

题意:给出一个数,问包含这个数三个数组成的勾股数,输出另外两个数。

思路:

所谓勾股数,就是当组成一个直角三角形的三边长都为正整数时,我们就称这一组数为勾股数. 那么,组成一组勾股数的三个正整数之间,是否具有一定的规律可寻呢?下面我们一起来观察几组勾股数: 规律一:在勾股数(3,4,5)、(5,12,13)、(7,24,25)(9,40,41)中,我们发现 由(3,4,5)有:32=9=4+5 由(5,12,13)有:52=25=12+13 由(7,24,25)有:72=49=24+25 由(9,40,41)有:92=81=40+41. 即在一组勾股数中,当最小边为奇数时,它的平方刚好等于另外两个连续的正整数之和.因此,我们把它推广到一般,从而可得出以下公式: ∵(2n+1)²=4n²+4n+1=(2n²+2n)+(2n²+2n+1) ∴(2n+1)²+(2n²+2n)²=(2n²+2n+1)²(n为正整数) 证明(略) 勾股数公式一:(2n+1,2n²+2n,2n²+2n+1)(n为正整数) 规律二:在勾股数(6,8,10)、(8,15,17)、(10,24,26)中,我们发现 由(6,8,10)有:62=36+2×(8+10) 由(8,15,17)有:82=64=2×(15+17) 由(10,24,26)有:102=100=2×(24+26) 即在一组勾股数中,当最小边为偶数时,它的平方刚好等于两个连续整数之和的二倍,推广到一般,从而可得出另一公式: ∵(2n)2=4n2=2[(n2-1)+(n2+1)] ∴(2n)2+(n2-1)2=(n2+1)2(n≥2且n为正整数) 证明(略) 勾股数公式二:(2n,n²-1,n²+1)(n≥2且n为正整数) 利用以上两个公式,我们可以快速写出各组勾股数.

结论是: n<=2无解。

n为奇数用公式1构造。

n为偶数用公式2构造。


代码实现
 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年08月20日 星期六 21时02分26秒
 4File Name :code/cf/#368/C.cpp
 5************************************************ */
 6#include <cstdio>
 7#include <cstring>
 8#include <iostream>
 9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <deque>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27using namespace std;
28const double eps = 1E-8;
29const int dx4[4]={1,0,0,-1};
30const int dy4[4]={0,-1,1,0};
31const int inf = 0x3f3f3f3f;
32LL n;
33int main()
34{
35	#ifndef  ONLINE_JUDGE
36//freopen("code/in.txt","r",stdin);
37  #endif
38    cin>>n;
39    if (n<=2)
40    {
41	puts("-1");
42	return 0;
43    }
44    if (n%2==0)
45    {
46	n/=2;
47	cout<<n*n-1<<" "<<n*n+1<<endl;
48    }
49    else
50    {
51	n--;
52	n/=2;
53	cout<<2*n*n+2*n<<" "<<2*n*n+2*n+1<<endl;
54    }
55  #ifndef ONLINE_JUDGE
56  fclose(stdin);
57  #endif
58    return 0;
59}

Related

hdu 5833 || ccpc 2016 网络赛 1002 Zhu and 772002 (高斯消元)

·528 words·2 mins
hdu 5833 题目链接 题意:n个数,保证每个数的素因子不超过2000,从中取若干个,问乘积是完全平方数的方案数。 思路: 完全平方数就是要求每个质因子的指数是偶数次。 列方程组,a1,a2,a3……am分别表示bi是否在集合中。对于每一个素因子,建立异或方程组,要求因子个数为偶数,即异或为0

hdu 2050 折线分割平面 (找规律,递推)

·246 words·1 min
hdu 2050题目链接 题意:n条折线。。最多能把平面分成几部分。。 思路:联想到m条直线,最多能把平面分成m*(m+1)/2+1部分。。 画图发现。。。 f[2*n-1]==g[n]。。

whust2016 warm up A ||codeforces 682 A. Alyona and Numbers (计数问题,水)

·294 words·1 min
cf682A题目链接 题意:两个数组,分别为1..n和1..m。。。从两个数组中各取一个,问和能被5整除的方案数。。。 思路:傻逼题。。。统计%5。。。然后乘法原理。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年07月18日 星期一 12时32分22秒 4File Name :code/2016whust/A.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E6+7; 34int n,m; 35LL a[N],b[N]; 36int main() 37{ 38 #ifndef ONLINE_JUDGE 39 freopen("code/in.txt","r",stdin); 40 #endif 41 42 cin>>n>>m; 43 ms(a,0); 44 ms(b,0); 45 for ( int i = 1 ; i <= n ; i++) 46 { 47 int x = i % 5; 48 a[x]++; 49 } 50 for ( int i = 1 ; i <= m ; i++) 51 { 52 int x = i % 5; 53 b[x]++; 54 } 55 LL ans = 0; 56 ans = a[0]*b[0]+a[1]*b[4]+a[2]*b[3]+a[3]*b[2]+a[4]*b[1]; 57 cout<<ans<<endl; 58 59 #ifndef ONLINE_JUDGE 60 fclose(stdin); 61 #endif 62 return 0; 63}

hdu 4607 Park Visit (树的直径,推公式)

·748 words·2 mins
hdu4607题目链接 题意:给出一棵树。。。边权都为1. m个查询。。每个查询给一个k,表示只访问k个点。。。问每次的最小路径和是多少。。。 思路:我们发现。。会使路径和变大的一个不利因素是折返。。也就是访问某景点后。。必须要回去才能继续前进。。这样的距离是2倍。。那为了使得路径和尽可能小。。我们就尽量不要访问这样的点。。。而不是这样的点一定在直径上。。。以及我们还发现。。。不在直径上的点。。 。。不管深度如何(深度的意思是说,与和该点最近的直径上的点的距离),距离的贡献是一样的。。都是2倍。。所以我们可以推出一个公式。。。如果树的直径是d,那么k<=d+1的时候,答案为k-1,否则答案为d+(k-d-1)*2。。。