https://ac.nowcoder.com/acm/contest/327/I
C++版本一
std
题解:数论
参考文章:https://blog.csdn.net/weixin_43272781/article/details/85558253
#include <bits/stdc++.h>
using namespace std;
int n;
int a[2005];
int b[2005];
int f(int x)
{
int ans=0;
for (int i=1;i*i<=x;i++)
{
if (x%i==0)
{
if (i*i==x)
{
ans++;
}
else
{
ans+=2;
}
}
}
return ans;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for (int i=1;i<=n;i++)
{
b[i]=f(a[i]);
}
int ans=0;
for (int i=1;i<=n;i++)
{
for (int j=i+1;j<=n;j++)
{
int x=a[i];
int y=a[j];
int fx=b[i];
int fy=b[j];
if (fx>fy)
{
swap(x,y);
swap(fx,fy);
}
if (x==1 || y==1)
{
int k=fx*fy;
if (k<=10) ans++;
}
else if (fx==2)
{
int k=y;
int cnt=0;
while (k%x==0)
{
k/=x;
cnt++;
}
if (fy/(cnt+1)*(cnt+2)<=10) ans++;
}
else if (fx==3)
{
if (fy==3)
{
ans++;
}
else
{
int xx=(int)(sqrt(x)+0.5);
int k=y;
int cnt=0;
while (k%xx==0)
{
k/=xx;
cnt++;
}
if (fy/(cnt+1)*(cnt+3)<=10) ans++;
}
}
else if (fx==4)
{
if (x==y) ans++;
else
{
int xx=(int)(pow(x,1.0/3)+0.5);
if (xx*xx*xx==x)
{
int k=y;
int cnt=0;
while (k%xx==0)
{
k/=xx;
cnt++;
}
if (fy/(cnt+1)*(cnt+4)<=10) ans++;
}
else
{
swap(x,y);
swap(fx,fy);
int xx=(int)(pow(x,1.0/3)+0.5);
if (xx*xx*xx==x)
{
int k=y;
int cnt=0;
while (k%xx==0)
{
k/=xx;
cnt++;
}
if (fy/(cnt+1)*(cnt+4)<=10) ans++;
}
swap(x,y);
swap(fx,fy);
}
}
}
else if (fx==5)
{
if (fy==5)
{
if (x==y) ans++;
}
else if (fy==6)
{
if (y%x==0) ans++;
}
}
}
}
printf("%d\n",ans);
return 0;
}