做计数 求有多少个不同的正整数三元组

链接：https://ac.nowcoder.com/acm/contest/3003/E

做计数

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <math.h>
#include <map>
#define mo 1000000007
using namespace std;
typedef long long ll;

int ans[7006];

void init()
{
    int i, j, n, an, cnt;
    ans[1] = 1;
    for(i = 2; i <= 6350; i++)   //对 4*10^7 开根大概是6324
    {
        n = i*i;
        an = 1;
        for(j = 2; j*j <= n; j++)
        {
            if(n%j == 0)
            {
                cnt = 0;
                while(n%j == 0)
                {
                    n /= j;
                    cnt++;
                }
                an = an * (cnt+1);
            }
        }
        if(n > 1)
            an *= 2;  // 根据唯一分解定理快速求 n 的因子个数
        ans[i] = ans[i-1] + an;   // 只要再加上这个完全平方数的因子个数就可以
    }
}

int main()
{
    int n, a;
    init();
    while(~scanf("%d", &n))
    {
        a = (int)sqrt(n);
        printf("%d\n",ans[a]);
    }
    return 0;
}

根据多年题感， 容易将所给等式两边平方得到 i + j + 2√(ij) = k, 虽然题目没说， 但我猜（滑稽），I, j, k 是整数，所以 ij 必须是完全平方数，设 m = ij; 因为 i, j, k 只要有一个不同就是不同的答案，所以 i, j 可以交换位置算一个答案，那么答案就是 1~m 之间所以完全平方数的因子个数之和，比如

同时可以知道在(i-1)(i-1) 和 ii 之间的输入正整数的符合答案与(i-1)(i-1) 的答案相同