题解 | #E做计数#

这题本蒟蒻是通过筛法ac的

我们考虑将原等式 $\sqrt i+\sqrt j=\sqrt k$ 平方有：

i+j+2\sqrt{ij}=k

注意到 $k$ 并没有限制，且 $i+j+2\sqrt{ij}\in\mathbf{Z}$

即 $\sqrt{ij}\in\mathbf{Z} \to \exists x\in[1,n](x^2=ij)$

欲统计原方程的个数即是统计对于每个 $x\in[1,n]$ 的因数对的个数

那么我们马上会想出直接线筛质数和因数个数 $d(x^2)$ 但是这样会TLE😭

然后会想到筛至sqrt(n)

考虑此时对于每个 $x$ 的因数分解：

x=\prod_{i=1}^n p_i^{q_i} \Longrightarrow d(x)=\sum p_i

以及 $x^2$ 的因数分解

\begin{aligned} x^2&=\prod_{i=1}^m p_i^{{q'}_i} \\ &=(\prod_{i=1}^n p_i^{q_i})^2 \\ &=\prod_{i=1}^n p_i^{2q_i} \Longrightarrow d(x^2)=\sum (2p_i+1) \end{aligned}

那么我们先线筛筛出质数同时统计每个数第一个非1因数spf，然后枚举x:=1~sqrt(n)求出 $d(x^2)$

最后直接ans+=d(x*x)

这题给出代码

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'

vector<ll> pri;
vector<bool> not_pri;
vector<ll> spf;

void pre(ll n)
{
   not_pri.resize(n+1,false);
   spf.resize(n+1,0);
   not_pri[0]=not_pri[1]=true;
   spf[1]=1;
   for(ll i=2; i<=n; i++)
   {
   	if(!not_pri[i])
   	{
   		pri.push_back(i);
   		spf[i]=i;	
   	}
   	for(ll p:pri)
   	{
   		if(i*p>n)break;
   		spf[i*p]=p;
   		not_pri[i*p]=true;
   		if(i%p==0)break;
   	}
   }
}


int main()
{
   ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   ll n,ans=0;
   cin >> n;
   ll sup=sqrtl(n);
   pre(sup);
   for(ll i=1; i<=sup; i++)
   {
   	ll x=i, prod=1;
   	while(x>1)
   	{
   		ll p=spf[x];
   		int cnt=0;
   		while(x%p==0){x/=p; cnt++;}
   		prod*=(2*cnt+1);
   	}
   	ans+=prod;
   }
   cout << ans << endl;
   


   return 0;
}