{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
plaincopy
- #include <stdio.h>
- #include <iostream>
- #include <string>
- using namespace std;
- class Test {
- public:
- static long Count (int a,int b){
- int res=0;
- int *resA=new int[b-a+1];
- for(int i=0;i<=b-a;++i)
- resA[i]=0;
- for(int p=1;p<=b;++p){
- int start=p/4+1;
- int q=4*start-p;
- int p3=p/3+2;
- while(q<=b){
- int tmp=p*q;
- if(tmp>b)break;
- if(q>=p3){
- if(tmp>=a)
- ++resA[tmp-a];
- }
- q+=4;
- }
- }
- for(int i=0;i<=b-a;++i)
- res+=resA[i]*(resA[i]-1);
- res/=2;
- return res;
- }
- };
- //start 提示：自动阅卷起始唯一标识，请勿删除或增加。
- int main()
- {
- cout<<Test::Count(1,30)<<endl;
- return 0;
- }
- //end //提示：自动阅卷结束唯一标识，请勿删除或增加。
显然复杂度为sum (1/4*b/i),i=1....b,根据调和级数得,O(blogb)