51nod 1165 整边直角三角形的数量（两种解法）

　链接：http://www.51nod.com/Challenge/Problem.html#!#problemId=1165

　直角三角形，三条边的长度都是整数。给出周长N，求符合条件的三角形数量。

　例如：N = 120，共有3种不同的满足条件的直角3角行。分别是：{20,48,52}, {24,45,51}, {30,40,50}。

　输入：

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 50000)

第2 - T + 1行：每行1个数N(12 <= N <= 10^7)。
输出：

输出共T行，每行1个对应的数量。

解法1：所有本原直角三角形（即边为a、b、c，gcd（a，b，c）==1）可表示为两奇数s和t,s>t，gcd(s,t)==1, 边为st，(s*s-t*t)/2,(s*s+t*t)/2
反之，任意符合条件的s，t也可通过这样组成本原直角三角形
所以周长C= s*(s+t) ，对于C<=1e7,发现是s是sqrt级别的,可以s^2暴力求gcd即O（n*gcd复杂度），求出所有在数据范围内的本原直角三角形的周长
那么对于一个周长n，不同的直角三角形必定对应着不同的本原直角三角形，所以本原直角三角形周长必定是n的因子，枚举n的因子，然后统计答案

#include<bits/stdc++.h>

#define mst(a,b) memset(a,b,sizeof(a))

#define lowbit(x) (x&(-x))

#define lson        (rt<<1)

#define rson        (rt<<1|1)

using namespace std;

typedef long long ll;

typedef long long LL;

typedef unsigned long long ull;

typedef pair<ll,ll> pll;

typedef pair<ll,int>pli;

typedef pair<int,int> pii;

const int inf = 0x3f3f3f3f;

const ll INF = 0x3f3f3f3f3f3f3f3f;

const int maxn = 1e7+;

const int mod = 1e9+;

int mi[maxn],use[maxn],ggg[maxn];

void init(int c=maxn-){

    int cc=;

    for(int i=; i<=c; ++i) {

        if(!mi[i])use[++cc]=i,mi[i]=i;

        int to=c/i;

        for(int j=; j<=cc and use[j]<=to; ++j) {

            mi[use[j]*i]=use[j];

            if(i%use[j]==) break;

        }

    }

    int u=sqrt(c);

    for(int i=;i<=u;i+=){

        int to=min(i-,(c-i*i)/i);

        for(int j=;j<=to;j+=){

            if(__gcd(i,j)==){

                ++ggg[i*(i+j)];

            }

        }

    }

}

int f[],cnt[],cc;

int d[],gg;

void dfs(int cur,int now){

    if(cur>cc){

        d[++gg]=now;

    }else{

        for(int i=;i<=cnt[cur];++i){

            dfs(cur+,now);

            now*=f[cur];

        }

    }

}

int solve(int val,int ti){

    int res=;

    int tmp=val;

    cc=;

    while(tmp>){

        int v=mi[tmp];

        f[++cc]=v;

        cnt[cc]=;

        while(tmp%v==){

            ++cnt[cc];

            tmp/=v;

        }

    }

    gg=;

    dfs(,);

    for(int i=;i<=gg;++i)

        res+=ggg[d[i]];

    return res;

}

int main() {

#ifdef local

    freopen("in.txt","r",stdin);

//    freopen("out.txt","w",stdout);

#endif

    ios::sync_with_stdio(false);

    cin.tie();

    cout.tie();

    init();

    int T;cin>>T;

    for(int i=;i<=T;++i){

        int val;cin>>val;

        if(val&)cout<<<<"\n";

        else cout<<solve(val,i)<<"\n";

    }

    return ;

}

解法2：化式子
　　a*a+b*b = c*c
　　a+b+c = n
-> a+b+sqrt(a*a+b*b) = n
-> sqrt(a*a+b*b) = n-a-b
-> 两边平方并化简
-> n^2 - 2an = 2bn-2ab
-> b = (n^2-2an)/(2n-2a)

令f = n-a
则 b = n(2n-2a -n)/(2f) = n(2f - n)/(2f) = n- n^2/(2f)
则有2f | n^2
再看适用范围，有
0 < a < n/3
a < b (不会有等于，abc都是整数，a=b，c=sqrt(2)a  × )
得到 n > f > 2n/3  ->  2n > 2f > 4n/3
n-f < n-n^2/(2f)  ->  2f^2 > n^2  -> 2f > sqrt(2)n > 4n/3
所以 sqrt(2)n < 2t < 2n
当2t确定，a也确定了
所以在n^2的因子中找符合条件的数

#include<bits/stdc++.h>

#define mst(a,b) memset(a,b,sizeof(a))

#define lowbit(x) (x&(-x))

#define lson        (rt<<1)

#define rson        (rt<<1|1)

using namespace std;

typedef long long ll;

typedef long long LL;

typedef unsigned long long ull;

typedef pair<ll,ll> pll;

typedef pair<ll,int>pli;

typedef pair<int,int> pii;

const int inf = 0x3f3f3f3f;

const ll INF = 0x3f3f3f3f3f3f3f3f;

const int maxn = 1e7+;

const int mod = 1e9+;

int mi[maxn],use[maxn],ggg[maxn];

inline int gcd(int a,int b){

    return b?gcd(b,a%b):a;

}

void init(int c=maxn-){

    int cc=;

    for(int i=; i<=c; ++i) {

        if(!mi[i])use[++cc]=i,mi[i]=i;

        int to=c/i;

        for(int j=; j<=cc and use[j]<=to; ++j) {

            mi[use[j]*i]=use[j];

            if(i%use[j]==) break;

        }

    }

//    int u=sqrt(c);

//    for(int i=3;i<=u;i+=2){

//        int to=min(i-1,(c-i*i)/i);

//        for(int j=1;j<=to;j+=2){

//            if(gcd(i,j)==1){

//                ++ggg[i*(i+j)];

//            }

//        }

//    }

}

int f[],cnt[],cc;

ll d[],gg;

void dfs(int cur,ll now){

    if(cur>cc){

        d[++gg]=now;

    }else{

        for(int i=;i<=cnt[cur];++i){

            dfs(cur+,now);

            now*=f[cur];

        }

    }

}

int solve(int val,int ti){

    int res=;

    int tmp=val;

    cc=;

    while(tmp>){

        int v=mi[tmp];

        f[++cc]=v;

        cnt[cc]=;

        while(tmp%v==){

            ++cnt[cc];

            tmp/=v;

        }

        cnt[cc]<<=;

    }

    gg=;

    dfs(,);

    int l=sqrt()*val,r=val<<;

    for(int i=;i<=gg;++i){

        ll v=d[i];

        if(v&)continue;

        if(v>l and v<r)++res;

    }

    return res;

}

int main() {

#ifdef local

    freopen("in.txt","r",stdin);

//    freopen("out.txt","w",stdout);

#endif

    ios::sync_with_stdio(false);

    cin.tie();

    cout.tie();

    init();

    int T;cin>>T;

    for(int i=;i<=T;++i){

        int val;cin>>val;

        if(val&)cout<<<<"\n";

        else cout<<solve(val,i)<<"\n";

    }

    return ;

}

发现两种解法的运行速度差不多。。。

巴特西

51nod 1165 整边直角三角形的数量（两种解法）

最新文章

热门文章