題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)正整數(shù) n ，求滿足條件 ( i , j , k ) 的三元組的數(shù)量，其中需要滿足：

sqrt( i ) + sqrt ( j ) = sqrt( k )

i * j <= n

n 的范圍是 4e7

題目分析：比賽的時(shí)候只想到了nsqrt(n)的枚舉方案，還是怪我太弱了，其實(shí)先要對(duì)原式進(jìn)行化簡(jiǎn)，兩邊同時(shí)平方得到：

這樣一來只需要枚舉 i * j就好了，滿足 i?* j 為完全平方數(shù)，且 i 和 j 都是正整數(shù)，可以兩層循環(huán)解決，外面一層枚舉每個(gè)完全平方數(shù)，時(shí)間復(fù)雜度為 sqrt( n )，內(nèi)部的循環(huán)枚舉每個(gè)完全平方數(shù)的因子個(gè)數(shù)，時(shí)間復(fù)雜度同為 sqrt( n )，套起來就是O(n)了，因?yàn)?i,j,k)和(j,i,k)為兩種答案，所以每次遇到可以整除的因子時(shí)貢獻(xiàn)累加 2 ，最后別忘了特判一下 i == j 的情況就好了

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;int main() { //#ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); //#endif // ios::sync_with_stdio(false);int n;scanf("%d",&n);int ans=0;for(int i=1;i*i<=n;i++)//枚舉完全平方數(shù){for(int j=1;j*j<i*i;j++)//枚舉完全平方數(shù)的因子 if((i*i)%j==0)ans+=2;ans++;} printf("%d\n",ans);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的牛客 - 做计数(数学)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。