算法_三元组的数量

{5 3 1}和{7 5 3}是2组不同的等差三元组,除了等差的性质之外,还有个奇妙的地方在于:5^2 – 3^2 – 1^2 = 7^2 – 5^2 – 3^2 = N = 15。

{19 15 11}同{7 5 3}这对三元组也存在同样的性质:19^2 – 15^2 – 11^2 = 7^2 – 5^2 – 3^2 = N = 15。

这种成对的三元组还有很多。当N = 15时,有3对,分别是{5 3 1}和{7 5 3},{5 3 1}和{19 15 11},{7 5 3}和{19 15 11}。


现给出一个区间 [a,b]求a <= N <= b 范围内,共有多少对这样的三元组。(1 <= a <= b <= 5*10^6)

例如:a = 1,b = 30,输出:4。(注:共有4对,{5 3 1}和{7 5 3},{5 3 1}和{19 15 11},{7 5 3}和{19 15 11},{34 27 20}和{12 9 6}) 

我的解法:

(1)首先为a到b的每个N值设置一个统计量,可以通过数组实现;

(2)三元组由起始值x和等差确定,即 x,x+d,x+2d,我们可以通过统计x和d来求得N,并将相应的统计量+1;

(3)最后统计对应每个N值的三元组数量,即可解题。

但是这样x和d无法枚举,继续:

由上面得(x+2d)^2-(x+d)^2-x^2=-x^2+2dx+3d^2=(3d-x)(x+d)=N;

另设p=3d-x ;   q=x+d; 那么得:p*q=N  ;   d=(p+q)/4; x=(3q-p)/4;

(注:上面在给a = 1,b = 30例子时没有给{0,3,6}与{12,9,6}这对,说明x的起始值应大于0)

所以得出下面四个限制条件:

1) p+q能被4整除;

2) 3q-p大于等于4;(条件1、2能推出3q-p能被4整除:因为3q-p+p+q=4p)

3) a=<p*q<=b

4)p,q是正整数

由上面4个限制条件我们可以通过枚举p、q来计算出相应的N值,将相应的统计量+1;

你是否会想当不同的p、q计算相同N值的时候是否会是同一个三元组?那么我们假设存在这种情况,那么:

x1=(3*q1-p1)/4  ==  x2=(3*q2-p2)/4 ;

d1=(p1+q1)/4    ==  d2=(p2+q2)/4 ;

解得p1==p2; q1==q2

所以说明只有当p、q两个值都相同时才对应同一个三元组,所以通过枚举p、q,利用上面的4个限制条件解题,转换为C++代码为:

  1. #include <stdio.h>  
  2. #include <iostream>  
  3. #include <string>  
  4. using namespace std;  
  5. class Test {  
  6. public:  
  7.     static long Count (int   a,int   b){  
  8.         int res=0;  
  9.         int *resA=new int[b-a+1];  
  10.         for(int i=0;i<=b-a;++i)  
  11.             resA[i]=0;  
  12.         for(int p=1;p<=b;++p){  
  13.             int start=p/4+1;          
  14.             int q=4*start-p;  
  15.             int p3=p/3+2;  
  16.             while(q<=b){  
  17.                 int tmp=p*q;  
  18.                 if(tmp>b)break;  
  19.                 if(q>=p3){  
  20.                     if(tmp>=a)  
  21.                         ++resA[tmp-a];  
  22.                 }  
  23.                 q+=4;  
  24.             }  
  25.         }  
  26.         for(int i=0;i<=b-a;++i)  
  27.             res+=resA[i]*(resA[i]-1);  
  28.         res/=2;  
  29.         return res;  
  30.     }  
  31.   
  32. };  
  33. //start 提示:自动阅卷起始唯一标识,请勿删除或增加。  
  34. int main()  
  35. {     
  36.     cout<<Test::Count(1,30)<<endl;    
  37.     return 0;  
  38. }   
  39. //end //提示:自动阅卷结束唯一标识,请勿删除或增加。  

显然复杂度为sum (1/4*b/i),i=1....b,根据调和级数得,O(blogb)

上一篇:ORACLE ASM 存储磁盘管理


下一篇:ORACLE AWR 生成常用脚本