取模 数论分块
取模
https://ac.nowcoder.com/acm/contest/30532/K
思路：首先化简一下该式子，原式=sum(n-n/i*i) = n*n-sum(n/i*i);
由数论分块可知，对于n/i而言，在0-n内一定存在一块连续的区间 l - r 在这段区间内 n/i 的值是相同的，
那么在这段区间内sum(n/i*i) = n/i * sum(i)；就相当于求 l - r 的区间和 即(r + l) * (r - l + 1) / 2;
因此问题就变成了求每一段区间 l 和 r; 而每一段的 l 等于上一段的 r + 1，r = n / ( n / l);
查看16道真题和解析
海康威视二面97人在聊
