牛客2020寒假训练营2-E

牛客2020寒假训练营2-E

七月 15, 2020

E.做计数

题意
求有多少个不同的正整数三元组 i j k
满足 sqrt(i)+sqrt(j)=sqrt(k) —— 等式1 且 i×j<=n;
三元组满足 i1!=i2 or j1!=j2 or k1!=k2视为不同

将等式1两边平方 发现 i+j+sqrt(i×j)=k
sqrt(i×j)<=sqrt(n);
枚举 i×j 再枚举i

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# include<bits/stdc++.h>

using namespace std;
typedef long long ll;

# define endl '\n'

int main(){
    int n;cin>>n;int cnt=0;
    for(int ij=1;ij*ij<=n;ij++){
        int ji=ij*ij;
        for(int i=1;i*i<=ji;i++){
            if(ji%i)continue;
            if(ji/i!=i)cnt+=2;
            else cnt++;
        }
    }
    cout<<cnt<<endl;
}