算法_三元组的数量

{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++代码为：

[cpp]  view plain copy

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)