P2424 約數和 題目提供者曹彥臣 難度 普及+/提高 題目背景 Smart最近沉迷于對約數的研究中。 題目描述 對于一個數X，函數f(X)表示X所有約數的和。例如：f(6)=1+2+3+6=12。對于一個X，Smart可以很快的算出f(X)。現在的問題是，給定兩個正整數X,Y(X
/*暴力線性遞推.*/#include<iostream>#define LL long longusing namespace std;LL ans,x,y;int main(){ cin>>x>>y; for(int i=1;i<=x-1;i++) ans-=(x-1)/i*i; for(int i=1;i<=y;i++) ans+=y/i*i; cout<<ans; return 0;}/*這題正解蠻神的.暴力的話就nsqrt(n)對每個數進行質因數分解.然后我們考慮優化.我們知道1-n中i的倍數有[n/i]個.然后我們就可以線性遞推了.但是這樣依然過不了此題.我們令s[i]=f[1]+f[2]+f[3]+..... =[i/1]*1+[i/2]*2+[i/3*3]+.....然后我們會發現里邊有些值是相同的.so 我們可以用等差數列加速.ans=s[y]-s[x-1].復雜度sqrt(n). */#include<iostream>#define LL long longusing namespace std;LL ans,x,y;LL slove(LL n){ LL i=1,tot=0; while(i<=n) { int j=n/(n/i); tot+=n/i*(j-i+1); i=j+1; } return tot;}int main(){ cin>>x>>y; cout<<slove(y)-slove(x-1); return 0;}新聞熱點
疑難解答
