题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1257
题意:计算sigama(m%i)(1<=i<=n)。
思路:
这样就简单了,若n*n<=m则可以直接暴力;否则,设t=sqrt(m),[1,t]之间暴力。在i大于t时我们发现,会出现成段的i使得m/i相同,那么我们直接枚举这个值i,那么L=m/(i+1)+1,R=m/i这个区间[L,R]的数字x均满足m/x=i,因此可以成段计算,复杂度也是O(sqrt(m))。
i64 n,m;
i64 cal()
{
i64 ans=0,i;
if(n<=100000)
{
FOR1(i,n) ans+=m/i*i;
return ans;
}
i64 t=sqrt(1.0*m+0.5);
FOR1(i,t) ans+=m/i*i;
i64 L,R;
FOR1(i,t)
{
L=m/(i+1)+1;
R=m/i;
if(L>n) continue;
if(R>n) R=n;
ans+=i*(L+R)*(R-L+1)/2;
}
return ans;
}
int main()
{
while(scanf("%lld%lld",&n,&m)!=-1) PR(n*m-cal());
}