生活随笔
收集整理的這篇文章主要介紹了
HDU3939(毕达哥拉斯三元组的解)
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
對于方程：，滿足條件：x，y，z兩兩互素的正整數(shù)解為：
?
，其中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;
}
總結(jié)
以上是生活随笔為你收集整理的HDU3939(毕达哥拉斯三元组的解)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
