首页 > 搜索 > DFS搜索 > HDU 3939-Sticks and Right Triangle-DFS-[解题报告]HOJ
2015
04-14

HDU 3939-Sticks and Right Triangle-DFS-[解题报告]HOJ

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
Hint
In 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.

对于方程:Sticks and Right Triangle,满足条件:x,y,z两两互素的正整数解为:

 

Sticks and Right Triangle,其中m>n>0,gcd(m,n)=1,m,n一奇一偶。


典型题目:POJ1305,HDU3939

 

对于POJ1305很简单,下面重点来解析HDU3939题。


题目:Sticks and Right Triangle

#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;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acdreamers/article/details/7921839


  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)