很考驗智商的一個題目，賽后看完別人的題解后秒懂了。

首先定義一個函數(shù)f(x)表示a,b的有序組合情況數(shù)使得a*b為x的一個約數(shù)。

現(xiàn)在給定你一個n，要你求出f(1)+f(2)+……+f(n)；

題目智商味道太濃厚，本屌表示智商拙計。

可以這樣來考慮問題，a*b為x的一個約數(shù)，其實就等價于a*b*c=x，c為任意一個正整數(shù)。

所以整個問題轉化為有多少個有序數(shù)對(a,b,c)使得a*b*c不大于n。

到這里問題就變得好辦多了。

由于直接枚舉復雜度過高，我們在枚舉的時候可以假定a<=b<=c，同時把中間a，b，c是否相等的情況都記錄下來。

這樣在求解答案的時候只要排列一下就可以了。

所以我們在枚舉a的時候，只要枚舉的范圍就是1到n^(1/3)，b需要枚舉的范圍就是n^(1/3)到n^(2/3)，這樣算來整個題目的時間復雜度為n^(2/3)大約為2*10^7，可以承受的哦。

題目注意統(tǒng)計的時候，盡量避免不必要的運算。

?

?

1 #include <cstdio> 2 using namespace std; 3 typedef long long ll; 4 ll n,m,k,ans,i,j; 5 int k1,k2,cas=0; 6 7 int main() 8 { 9 while (scanf("%I64d",&n)!=EOF) 10 { 11 ans=0; 12 for (i=1; i*i*i<=n; i++) ; 13 ans+=--i; 14 for (; i; i--) 15 { 16 m=n/i; 17 for (j=1; j*j<=m; j++) ; 18 ans+=3*(m/i-i+--j-i); 19 for (; j>i; j--) ans+=6*(m/j-j); 20 } 21 printf("Case %d: %I64d\n",++cas,ans); 22 } 23 return 0; 24 }

?

?

?

轉載于:https://www.cnblogs.com/lochan/p/3398429.html

總結

以上是生活随笔為你收集整理的HDU4473_Exam的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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