Codeforces 707C. Pythagorean Triples-推公式的数学题

两道C题题解，能推出来公式简直是无敌。

http://codeforces.com/problemset/problem/707/C

codeforces707C. Pythagorean Triples

这个题就是直角三角形的三条边，给你一条边的长度，让你输出其他两边的长度。

会发现有规律。当数为奇数时，就是平方除以2，然后另一边再加上1就可以。

偶数的时候一直除以2，直到4为止，然后特判就可以，再用一下快速幂就可以了。

代码:

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<queue>
 5 #include<algorithm>
 6 using namespace std;
 7 typedef long long ll;
 8 ll kuaisumi(int a,int b){
 9     ll ans=1;
10     while(b!=0){
11         if(b%2==1)
12             ans=ans*a;
13             a=a*a;
14             b=b/2;
15     }
16     return ans;
17 }
18 int main(){
19     ll n;
20     cin>>n;
21     if(n==1||n==2)cout<<"-1"<<endl;
22     else{
23         int num=0;
24         while(n>4&&n%2==0){
25             num++;
26             n/=2;
27         }
28         //cout<<num<<endl;
29         ll cnt=kuaisumi(2,num);
30         if(n%2==1)cout<<n*n/2*cnt<<" "<<(n*n/2+1)*cnt<<endl;
31         else if(n%3==0)cout<<4*cnt<<" "<<5*cnt<<endl;
32         else if(n%4==0)cout<<3*cnt<<" "<<5*cnt<<endl;
33     }
34 }