P2424 約數(shù)和 題目提供者曹彥臣 難度 普及+/提高 題目背景 Smart最近沉迷于對約數(shù)的研究中。 題目描述 對于一個數(shù)X，函數(shù)f(X)表示X所有約數(shù)的和。例如：f(6)=1+2+3+6=12。對于一個X，Smart可以很快的算出f(X)。現(xiàn)在的問題是，給定兩個正整數(shù)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)對每個數(shù)進行質因數(shù)分解.然后我們考慮優(yōu)化.我們知道1-n中i的倍數(shù)有[n/i]個.然后我們就可以線性遞推了.但是這樣依然過不了此題.我們令s[i]=f[1]+f[2]+f[3]+..... =[i/1]*1+[i/2]*2+[i/3*3]+.....然后我們會發(fā)現(xiàn)里邊有些值是相同的.so 我們可以用等差數(shù)列加速.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;}新聞熱點
疑難解答
