做计数

做计数
https://ac.nowcoder.com/acm/contest/3003/E

两边平方后可得 i+j+2(根号ij)=k，若k为正整数，则ij为完全平方数且ij<=n
遍历1到n可得ij为完全平方数时的数据，并求ij的因数和即得 O（nlogn)
或者直接遍历完全平方数 i*i<=n 为条件

#pragma warning (disable :4996)
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e7;

int n;
int B[maxn];
int sum = 0;
void Yin(int x) {
    for (int i = 1; i <= sqrt(x); i++) {
        if (x % i == 0) {
            if (i == x / i)
                sum++;
            else
                sum += 2;
        }
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i*i <= n; i++) {
        Yin(i * i);
    }
    cout << sum << endl;
}