シンプルな問題。
http://codeforces.com/contest/616/problem/E
問題
正整数N,Mが与えられる。
を答えよ。
解法
平方分割の要領で考える。
iが10^6の範囲は、愚直にN%iを計算して足しこんでいこう。
N = k*i+r (kが商, rが余り)とする。iがある程度大きくなると、あるiの区間でkが等しくなる。
Nをiで割った余りがkとなるiの区間を[L,R]とする。
求めたいのは上記rだが、これはN-k*iで計算できる。
kが同一となるi∈[L,R]に対してこの和は、で計算できる。
あとはkを0からN/(10^6)程度までループさせならが上記和を足しこんでいこう。
ll N,M; ll mo=1000000007; ll rev2 = (mo+1)/2; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; ll ret=0; ll g; for(g=1;g<=min(5000000LL,M);g++) { ret+=N%g; if(ret>=mo) ret-=mo; } if(M>5000000) { for(ll x=0;;x++) { ll L=max(N/(x+1)+1,g); ll R=min(M,(x?N/x:M)); if(R<g) break; if(L>R) continue; ll a=(N%mo)*((R-L+1)%mo)%mo; ll b=x*((L+R)%mo)%mo*((R-L+1)%mo)%mo*rev2%mo; ret+=mo+a-b; while(ret>=mo) ret-=mo; } } cout<<ret<<endl; }
まとめ
妙にバグ仕込んで辛かった。