2015
04-14

# Sticks and Right Triangle

We have a stick with infinite length. Now we want to cut 3 sub-sticks with length x, y, z which is not large than L to form a right triangle. With unknown reasons we assume that x, y, z are all integers and satisfy that x, y, z are all co-primed each other. We want to know how many right triangles are there exist under our constraints

The first line of input is an integer T (T<=5) indicating the number of test cases.
Each case contains a single integer L (L<=1,000,000,000,000).

The first line of input is an integer T (T<=5) indicating the number of test cases.
Each case contains a single integer L (L<=1,000,000,000,000).

1
5

1
HintIn our test case, we could find a right triangle (3,4,5) which satisfy 3,4,5<=5 and gcd(3,4)=1,gcd(3,5)=1,gcd(4,5)=1. 

，其中m>n>0，gcd(m,n)=1，m，n一奇一偶。

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>

using namespace std;
typedef long long LL;

const int N=1000005;

int p[N],phi[N];
bool prime[N];
int check[35];
int k,num;
LL ans,L;

void isprime()
{
k=0;
int i,j;
memset(prime,true,sizeof(prime));
for(i=2;i<N;i++)
{
if(prime[i])
{
p[k++]=i;
for(j=i+i;j<N;j+=i)
{
prime[j]=false;
}
}
}
}

void Init_phi()
{
int i,j;
for(i=1;i<N;i++)  phi[i]=i;
for(i=2;i<N;i+=2) phi[i]>>=1;
for(i=3;i<N;i+=2)
{
if(phi[i]==i)
{
for(j=i;j<N;j+=i)
{
phi[j]=phi[j]-phi[j]/i;
}
}
}
}

void prime_check(int n)
{
num=0;
if(prime[n])
{
check[num++]=n;
return;
}
for(int i=0;i<k&&n>1;i++)
{
if(n%p[i]==0)
{
check[num++]=p[i];
while(n%p[i]==0) n/=p[i];
if(n>1&&prime[n])
{
check[num++]=n;
return;
}
}
}
}

void dfs(int k,int r,int s,int n)
{
if(k==num)
{
if(r&1) ans-=n/s;
else    ans+=n/s;
return;
}
dfs(k+1,r,s,n);
dfs(k+1,r+1,s*check[k],n);
}

int main()
{
int T;
isprime();
Init_phi();
cin>>T;
while(T--)
{
ans=0;
cin>>L;
int m=(int)sqrt(1.0*L);
for(int i=m;i>0;i--)
{
int p=(int)sqrt(L-(LL)i*i);
if(i&1)
{
prime_check(i);
if(i<=p) dfs(0,0,1,i>>1);
else     dfs(0,0,1,p>>1);
}
else
{
if(i<=p) ans+=phi[i];
else
{
prime_check(i);
dfs(0,0,1,p);
}
}
}
cout<<ans<<endl;
}
return 0;
}


1. a是根先忽略掉，递归子树。剩下前缀bejkcfghid和后缀jkebfghicd，分拆的原则的是每个子树前缀和后缀的节点个数是一样的，根节点出现在前缀的第一个，后缀的最后一个。根节点b出现后缀的第四个位置，则第一部分为四个节点，前缀bejk，后缀jkeb，剩下的c出现在后缀的倒数第2个，就划分为cfghi和 fghic，第3部分就为c、c

2. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧

3. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
O(n) = O(n-1) + O(n-2) + ….
O(n-1) = O(n-2) + O(n-3)+ …
O(n) – O(n-1) = O(n-1)
O(n) = 2O(n-1)