BISHI42 余数求和

求解思路

由于对任意正整数k,ik, ik,i，有kmod i=k−i×⌊ki⌋k \mod i = k - i \times \lfloor \frac{k}{i} \rfloorkmodi=k−i×⌊ik​⌋

∑i=1n(kmod i)=∑i=1n(k−i×⌊ki⌋)=n×k−∑i=1min⁡(n,k)(i×⌊ki⌋)\sum_{i=1}^n (k \mod i) = \sum_{i=1}^n \left( k - i \times \lfloor \frac{k}{i} \rfloor \right) = n \times k - \sum_{i=1}^{\min(n,k)} \left( i \times \lfloor \frac{k}{i} \rfloor \right)i=1∑n​(kmodi)=i=1∑n​(k−i×⌊ik​⌋)=n×k−i=1∑min(n,k)​(i×⌊ik​⌋)

求解代码

publicstaticvoidmain(String[]args)throwsIOException{BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));PrintWriterout=newPrintWriter(newOutputStreamWriter(System.out));String[]str=br.readLine().split("\\s+");longn=Long.parseLong(str[0]);longk=Long.parseLong(str[1]);longtotal=n*k;// 原表达式的第一部分longm=Math.min(n,k);// 只需要计算到min(n,k)longi=1;while(i<=m){longv=k/i;longj=Math.min(k/v,m);// 当前块的右边界// 计算i到j的和：(i+j)*(j-i+1)/2，再乘以vtotal-=v*(i+j)*(j-i+1)/2;i=j+1;// 跳到下一个块}out.println(total);out.flush();out.close();br.close();}