2020牛客寒假算法基础集训营2 E做计数 详解思路
程序员文章站
2022-06-18 13:02:21
...
题目链接:https://ac.nowcoder.com/acm/contest/3003/E
题目:
思路:
将等式两边平方:
i+j+2*sqrt(i*j)=k
所以,当i*j为平方数时,正整数k存在。
即求:1~n的平方数的因子
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
int sum(int x)
{
int ans=0;
for(int i=1;i<=sqrt(x);i++)
{
if(x%i==0)
{
if(i*i==x) ans++; ///如果i,j相同,ans++
else ans+=2; ///如果i,j不同,ans+=2(i,j位置可以互换)
}
}
return ans;
}
int main()
{
int n;
scanf("%d",&n);
int ans=0;
for(int i=1;i*i<=n;i++) ///注意:这里要用i*i<=n,可降低复杂度
{
ans+=sum(i*i);
}
printf("%d\n",ans);
}
下一篇: pr怎么渲染导出最小体积的高清视频?