HDU 3939-Sticks and Right Triangle(毕达哥拉斯三元组+欧拉函数)-白红宇

HDU 3939-Sticks and Right Triangle(毕达哥拉斯三元组+欧拉函数)

阅读量：2029 次

发布时间：2019-04-28

本文共 1079 字，大约阅读时间需要 3 分钟。

题目地址：

题意：给出勾股方程X^2+Y^2=Z^2，满足X,Y,Z不超过L，问存在多少个解满足X,Y,Z两两互素。

思路：其实就是求有多少个毕达哥拉斯本原三元组，因为数据很大，所以不能像上一道题一样，直接暴力枚举。那下面我们来分析一下：

由X^2+Y^2+Z^2我们可以知道，方程的解为X=m^2-n^2，Y=2*m*n，Z=m^2+n^2，其中m>n，m与n一奇一偶，且gcd(m,n)=1。由式子我们可以知道Z最大，这样只需要Z=m^2+n^2<=L即可。所以我们可以确定一下m和n的大体范围，m<=sqrt(L) ;n<=sqrt(l-m*m)=Nmax。

1）当m为偶数,此时n为奇数：

1.如果m<=Nmax，那么n的取值就是[1,m)中与m互素的数的个数(m的欧拉函数值)；

2.如果m>Nmax，对m进行素因子分解，然后通过容斥原理来计算[1,Nmax)内与m互素的个数。

2）当m为奇数时，此时n为偶数：

1.如果m<=Nmax，那么n的选择就是[1,m/2)内与m互素的数的个数（这样我们乘以2以后得到的就一定是偶数了）；

2.如果m>Nmax，那么n的选择就是[1,Nmax/2)内与m互素的个数。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #pragma comment(linker, "/STACK:102400000,102400000")using namespace std;typedef __int64 LL;const int inf=0x3f3f3f3f;const double pi= acos(-1.0);const double esp=1e-6;using namespace std;const int Maxn=1e6+10;bitset
               
                pri;LL prime[Maxn];LL sprime[Maxn];LL phi[Maxn];LL k,cnt;void is_prime(){ pri.set(); for(LL i=2; i
                
                 1) sprime[cnt++]=n;}LL Ex(LL n){ LL ans=0; LL tmp,flag; LL i,j; for(i=1; i<(LL)(1<

转载地址：http://pcsaf.baihongyu.com/

你可能感兴趣的文章