欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2020牛客寒假算法基础集训营2 E做计数 详解思路

程序员文章站 2022-06-18 13:02:21
...

题目链接:https://ac.nowcoder.com/acm/contest/3003/E
题目:
2020牛客寒假算法基础集训营2 E做计数 详解思路
2020牛客寒假算法基础集训营2 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);
}

相关标签: 思路