2020牛客寒假算法基础集训营2-E 做计数

题目链接：https://ac.nowcoder.com/acm/contest/3003/E
题意是要找 并且i,j,k均为正整数 的数对数量，两边同时平方，我们就得到 ,其实也就是需要i,j的乘积是一个完全平方数，我们就直接在n的范围内寻找完全平方数再求一下它的因子数就行了，两次求因子，复杂度在O(n)
代码如下

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>

#define lson  rt << 1
#define rson  rt << 1 | 1
#define il inline
#define ll long long
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const ll inf = 0x7ffffffffff;
const ll mod = 1e9 + 7;

template<class T>
inline void read(T &res) {
    char c;
    T flag = 1;
    while ((c = getchar()) < '0' || c > '9')if (c == '-')flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')res = res * 10 + c - '0';
    res *= flag;
}

ll t;

ll qpow(ll a, ll b) {
    ll ans = 1;;
    a %= mod;
    while (b) {
        if (b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans % mod;
}
int main() {
    ll n,ans=0;
    cin>>n;
    for(ll i=1;i*i<=n;i++){
        ll res=0;
        for(ll j=1;j*j<=i*i;j++){
            if((i*i)%j==0) res++;
        }
        ans+=2*res-1;
    }
    cout<<ans<<endl;
    return 0;
}