Zeldain Garden

題意：

問[L,R]內所有數的因子的數量和

題解：

如果傳統暴力做肯定不行
我們來找找規律：

數字： 因子數目 1~n的因子數和 1 1 1 2 2 3=2+1/ 3 2 5=3+1+1 4 3 8=4+2+1+1 5 2 10=5+2+1+1+1 6 4 14= 7 2 16= 8 4 20= 9 3 23=9+4+3+2+1+1+1+1+1

有發現什么規律？
可以推出：1—n的因子數和 =∑ (int)n/i （i是從1到n）
問我咋推出來的？
額。。“直覺”算能力嗎？我在紙上把因子數和進行拆分就發現這樣的規律
但是注意題目中的數據是1e12，感覺直接做還是不準，，O(n)肯定不行，此時就要往O(log n)或者O(√n)的方向去想
∑ (int)n/i其實是函數y=n/x的一個離散和
而這個函數是關于y=x對稱，對稱點為（√n，√n），圖像面積是對稱的，所以我們只需要求出√n數據范圍內的答案即可，然后乘以2減去√n√n，其實就是去掉重復的正方形面積，正方形邊長是√n，這樣一來復雜度不就降低了，1e12就沒問題了
答案就是 ans2 - t *t
t=sqrt(n)
小于sqrtN的因子在所有數中有多少：∑N/i (i=1,…,sqrtN)
大于sqrtN的因子在所有數中有多少: ∑N/i (i=1,…,sqrtN)
但是兩者有重復部分
“因子對”里的數都小于sqrtN的那些因子其實被重復加了一遍，多加了Q * Q個因子

代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<map> #include<queue> using namespace std; typedef long long ll;//用long long ll work(ll n)//計算一個數的因子之和 {ll ans=0;ll t=sqrt(double(n));//根號nfor(int i=1;i<=t;i++){ans=ans+n/i;}ans=ans*2-t*t;//公式求和 } int main () {ios::sync_with_stdio(false);ll n,m;cin>>n>>m;cout<<work(m)-work(n-1)<<endl;//從n-m的，跟前綴和差不多原理return 0; }

總結

以上是生活随笔為你收集整理的2020牛客国庆集训派对day1 Zeldain Garden的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。