daimayuan 每日一题-平方计数

本文主要是介绍daimayuan 每日一题-平方计数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目link
学习博客

思路

a i 2 + a j = x 2 a_i^2+a_j=x^2 ai2​+aj​=x2
移项得： a j = x 2 − a i 2 a_j=x^2-a_i^2 aj​=x2−ai2​
平方差公式得: a j = ( x + a i ) ( x − a i ) a_j=(x+a_i)(x-a_i) aj​=(x+ai​)(x−ai​)
可以发现 a j a_j aj​ 为其两个因子的乘积且满足 ( x + a i ) − ( x − a i ) = 2 ∗ a i (x+a_i) - (x-a_i) = 2*a_i (x+ai​)−(x−ai​)=2∗ai​
1 e 6 1e6 1e6范围内数因子个数最多量级为 4000 4000 4000
那么可以枚举因子
利用短除法求因子 O ( n ∗ n ) O(n*\sqrt{n}) O(n∗n ​)可能会T，这里利用倍增 O ( n ∗ l o g ( n ) ) O(n*log(n)) 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;
}

这篇关于daimayuan 每日一题-平方计数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！