AT_abc342_d 题解
__graphite__
·
·
题解
UD 2024/2/24 22:36 感谢 Lixiang_is_potato 指出一处笔误。
本文同步发表于 cnblogs。
赛时挂了，但是赛后 3min AC，我是飞舞。
题意
给你一个长度为 N 的非负整数序列 A=(A_1,\ldots,A_N)。求满足以下两个条件的整数对 (i,j) 的个数：
~~懒得提交翻译~~
### 思路
显然，$A_i$ 的平方因子对他自己一点用都没有。
所以我们先给它的平方因子除掉，剩下的 $A_i$ 中相等的两两配对。
但要注意 $0$，它可以和其他任何数相乘（$0$ 也是平方数）！
### 代码
由于我的宏定义又臭又长我就删掉了。
```cpp
LL n,a[200010],ans,sum,f[200010];
int main()
{
cin>>n;
rep(i,1,n,1)
{
cin>>a[i];
for(LL j=2;j*j<=a[i];j++)//错
{
while(a[i]%(j*j)==0)
{
a[i]/=(j*j);
}
}
f[a[i]]++;
if(!a[i])ans++;
}
rep(i,0,200000,1)
{
sum+=f[i]*(f[i]-1)/2;
}
sum+=ans*(n-ans);
cout<<sum<<endl;
return 0;
}
```
### 小结
其实很感慨，赛时我代码里面打注释“错” 的那行我 $j$ 的初值设成 $1$ 了，调了好久… 导致直接掉分。
所以，衷心祝愿所有 OIer 能正常发挥，不犯太多错误，在比赛中取得好成绩！