[数据结构与算法]daimayuan 每日一题-平方计数

题目link
学习博客

思路

$a_i^2+a_j=x^2$
移项得： $a_j=x^2?a_i^2$
平方差公式得: $a_j=(x+a_i)(x?a_i)$
可以发现 $a_j$ 为其两个因子的乘积且满足 $(x+a_i)?(x?a_i)=2?a_i$
$1e6$范围内数因子个数最多量级为$4000$
那么可以枚举因子
利用短除法求因子$O(n?\sqrt{n})$可能会T，这里利用倍增$O(n?log(n))$求因子

for(int i = 1;i <= 1000000;i++)
	for(int j = i;j <= 1000000;j+= i)
// 第一层枚举一个因子 i , j/i为第二个因子，乘积为j  

code

int n;
int a[1000005];
int cot[1000005];
signed main()
{
    _orz;
    cin>>n;
    forr(i,1,n) cin>>a[i],cot[a[i]]++;

    int res = 0;
    // 倍数取因子;
    //  会出现两次  例如:   i = 1 j = 3 // i = 3 j = 3
    //  
    for(int i = 1;i <= 1000000;i++){
        for(int j = i;j <= 1000000;j+= i){
            int mi = min(j/i,i),ma = max(j/i,i);
            int d = ma-mi;
            if(d%2==0){
                res += cot[j]*cot[d/2];
                // if(cot[j] && cot[d/2])
                //     cout << j <<" "<< d/2 << endl;
            }
        }
    }
    cout << res/2 << '\n';
    return 0;
}